Alladi Ramakrishnan Hall

Using hardness-randomness connections in algebraic complexity

Anamay Gurunath Tengse

Reichman University, Herzliya

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 this has not translated into lower bounds for circuits, where the state-of-the-art remains to be Omega(n log n). This has led to some works (e.g. Forbes, Shpilka and Volk (2018)) that investigate whether algebraic circuit lower bounds admit a "barrier" similar to the boolean setting.

The 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 to be a trivial, exponential-time algorithm.

In this talk, we will first see how the above two questions are connected. I will then describe some of my works that utilize these connections to throw some light on the questions themselves. In particular, these works use hardness-randomness connections to reveal a "threshold behaviour" of identity testing, and gather some insights into the "barrier question".