Tata Institute of Fundamental Research

Lower Bounds for General Algebraic Circuits

STCS Student Seminar
Speaker: Prerona Chatterjee
Organiser: Neha Sangwan
Date: Friday, 15 Mar 2019, 17:15 to 18:15
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  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.