Closure under Factorization from a Result of Furstenberg
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.
Authors
- Shubhangi Saraf (ORCID: https://orcid.org/0009-0005-0874-2978)
- Somnath Bhattacharjee (ORCID: https://orcid.org/0009-0007-3124-4146)
- Varun Ramanathan (ORCID: https://orcid.org/0009-0002-5903-593X)
- Ramprasad Saptharishi (ORCID: https://orcid.org/0000-0002-7485-3220)
- Mrinal Kumar (ORCID: https://orcid.org/0000-0001-9747-9449)
- S. Rai (ORCID: https://orcid.org/0000-0002-4062-0111)
Institutions
- Tata Institute of Fundamental Research (IN)
- University of Toronto (CA)
Publication Details
- Published
- 2026-06-09
- DOI
- https://doi.org/10.1145/3798129.3800738
- Citations
- 1
- Primary Topic
- Polynomial and algebraic computation
- Type
- article
- Field-Weighted Citation Impact
- 15.59
Funders
- Department of Atomic Energy, Government of India