Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SOMNATH BHATTACHARJEE:
All reports by Author Somnath Bhattacharjee:

TR25-044 | 10th April 2025
Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

Deterministic factorization of constant-depth algebraic circuits in subexponential time

While efficient randomized algorithms for factorization of polynomials given by algebraic circuits have been known for decades, obtaining an even slightly non-trivial deterministic algorithm for this problem has remained an open question of great interest. This is true even when the input algebraic circuit has additional structure, for instance, when ... more >>>




ISSN 1433-8092 | Imprint