Multivariate polynomial factorization is a fundamental algebraic problem with connections to error-correcting codes, pseudorandomness and complexity theory. Constant-depth circuits form a restricted yet natural subclass of general polynomial-size arithmetic circuits, capturing a wide variety of algebraic problems. In this talk, we will try and understand some of the ideas that went into a recent line of work that concluded with a deterministic factorization algorithm for constant-depth circuits. More generally, we will see that for most natural algebraic models, deterministic (black-box) polynomial identity testing is sufficient for deterministic factorization.
At the heart of these algorithmic results, we will use polynomial identity testing to project multivariate polynomials to univariate polynomials while preserving information about the factors. The final algorithmic result in this line of work builds upon a recent surprising and important structural result: constant-depth circuits (and most natural algebraic models) are closed under factoring -- if a polynomial has a constant-depth circuit, then so do its factors.
This talk will be based on collaborations with Somnath Bhattacharjee, Mrinal Kumar, Shanthanu Suresh Rai, Ramprasad Saptharishi, Shubhangi Saraf and Ben Lee Volk.
