Closure under Factorization from a Result of Furstenberg

Proceedings of the 58th Annual ACM Symposium on Theory of Computing 2026 Open access

Read full text
Authors: Somnath Bhattacharjee, Mrinal Kumar, S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf
DOI: 10.1145/3798129.3800738
Cited by: 1
References: 35

Abstract

We show that algebraic formulas and constant-depth circuits are closed under taking factors. In other words, we show that if a multivariate polynomial over a field of characteristic zero has a small constant-depth circuit or formula, then all its factors can be computed by small constant-depth circuits or formulas respectively.

Fields of Study & Subjects

Polynomial and algebraic computation Complexity and Algorithms in Graphs Advanced Graph Theory Research

Publication details

Journal / source
Proceedings of the 58th Annual ACM Symposium on Theory of Computing
Publisher
ACM
Pages
174–185
Publication date
9 June 2026
Language
EN