Lower Bounds in Algebraic Circuit Complexity

Abstract:

Algebraic circuits and formulas are the standard computational models for computing multivariate polynomials. They are similar to boolean circuits and formulas except that in this case, gates are labelled by ‘+’ or ‘x’. Another important model is that of an algebraic branching program (ABP), which is an intermediate model between circuits and formulas in terms of computational power. I will begin the talk by defining these models of computation formally, and then survey some of the results that have helped shape our understanding of algebraic circuits.

Along the way, we will see that even though very strong lower bounds are known against various structured models, the best known lower bound against general algebraic circuits is barely super-linear [Str73, BS83]. This was also the best known bound against ABPs. On the other hand, against formulas, the best known lower bound was $\Omega(n^2/log n)$ [Kal85, SY11] for multilinear polynomials (which is the interesting case). In a joint work with Mrinal Kumar, Adrian She and Ben Lee Volk, we improved the bounds for ABPs and formulas by showing a quadratic lower bound against both these models. We will see the proof ideas of this result in some detail.