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)

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.