Lower Bounds for General Algebraic Circuits

Abstract:  The best known lower bound for general algebraic circuits was given by Baur and Strassen [BS83]. They showed that there exists an explicit n-variate, degree d polynomial such that the smallest fan-in 2 circuit computing it requires size Omega(n log d).

However, when d is constant, the above result only gives a linear lower bound. In this setting, Raz [Raz08] gave a super-linear lower bound of the following form. He showed that for any natural number d, there exists an explicit n-variate polynomial of degree O(d) such that the smallest depth-d circuit computing it requires size $n^{1 + Omega(1/d)}$.

In this talk, we will quickly go over the proof idea of the result by Baur-Strassen and then focus on Raz's super-linear lower bound for bounded depth circuits.