Please note: This seminar will take place in DC 1304 and online.
Shubhangi Saraf, Associate Professor
Departments of Mathematics and Computer Science, University of Toronto
I will talk about a recent result showing that algebraic formulas and constant-depth circuits are closed under taking factors. In other words, the complexity of factors of polynomials computable by algebraic formulas or constant depth algebraic circuits is not much more than the complexity of the original polynomial itself.
This result turns out to be an elementary consequence of a fundamental and surprising result of Furstenberg from the 1960s, which gives a non-iterative description of the power series roots of a bivariate polynomial. Combined with standard structural ideas in algebraic complexity, we observe that this theorem yields the desired closure results. We will see applications of this result to deterministic algorithms for factoring, hardness/randomness tradeoffs, as well as GCD computation of polynomials.
This talk is based on joint works with Somnath Bhattacharjee, Mrinal Kumar, Shanthanu Rai, Varun Ramanathan and Ramprasad Saptharishi.
To attend this seminar in person, please go to DC 1304. You can also .