Alladi Ramakrishnan Hall

Lower Bounds for some Algebraic Models of Computation

Prerona Chatterjee

Tel Aviv University

Algebraic circuits and formulas are two of the most natural models for computing polynomials, and proving super- polynomial lower bounds against these models are central questions in the field of complexity theory. A long line of works culminating in the recent breakthrough work of Limaye, Srinivasan and Tavenas proved the first super-polynomial lower bound against constant depth algebraic circuits and formulas. However, proving lower bounds in the general case continues to remain widely open. Another important model for computing polynomials is that of algebraic branching programs, whose power lies in between that of circuits and formulas.

In this talk we will discuss the current state-of-the art for lower bounds against these models of computation in the general as well as some structured settings. I will then describe two of my recent works, one with Hrubes (CCC 2023) and another with Kush, Saraf and Shpilka (under submission), in greater detail; and conclude with some future directions that I am excited about.