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.
| 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.
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.