| Title | : | Using Hardness-Randomness Connections in Algebraic Complexity |
| Speaker | : | Anamay Tengse (Postdoc @ Reichman University, Israel) |
| Details | : | Mon, 24 Jun, 2024 2:00 PM @ SSB-334 |
| Abstract: | : | Finding explicit polynomials that require circuits of super-polynomial size is a major open question in algebraic complexity. Over the years, this question has seen significant progress in various structured settings, but that has not translated into lower bounds for circuits, where the state-of-the-art remains to be Ω(n log n). This has led to some works (e.g. Forbes, Shpilka and Volk (2018)), which investigate whether algebraic circuit lower bounds admit a "barrier" similar to the boolean setting. A closely related question of blackbox identity testing asks for a deterministic query algorithm that determines if the circuit being queried computes the "unsatisfiable" zero polynomial. Here again, the state-of-the-art for circuits remains a trivial, exponential algorithm. In this talk, we will first see how the above questions are connected. We will then look at some of my works that utilize these connections, to throw some light on the questions themselves. The works deal with two themes: a "threshold behaviour" of identity testing and understanding the possibility of a "barrier" as mentioned above. |
