Seminar: Depth-Three Circuits: Recent Constructions and Lower Bounds, and the Road Ahead
Abstract: Valiant's seminal work in 1976 showed that depth-3 circuits non-trivially capture unrestricted computation. In particular strong exponential lower bounds for depth-3 circuits imply non-linear lower bounds for (almost) general circuits, a frontier in complexity theory. However, the state-of-the-art lower bounds have not changed since the 80s. In the past few years, we have developed a new program and techniques to make progress in this front. In this talk I will outline these results.
Bio sketch: Navid Talebanfard from Univeristy of Sheffield will be host in the department from April 16th to April 21th. He will give a talk Friday April 17 in Room A4 at 11:30 (right after the teaching meeting) about his recent results obtained with Mohan Paturi, Mike Sacks, Daniel Kleber and Chirs Rosin about optimal depth three boolean circuits and new lower bounds techniques for boolean circuits.