Top-level heading

Depth-Three Circuits: Recent Constructions and Lower Bounds, and the Road Ahead

Categoria
Altro (categoria non censita)
Categoria non censita
Sapienza LoC3 Seminar (Logic, Complexity, Combinatorics and Computability)
Data e ora inizio evento
Data e ora fine evento
Sede

DIAG (Via Ariosto 20. Metro A - Manzoni)

Aula esterna
Aula 4
Speaker
Navid Talebanfard (University of Sheffield)
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.
Contatti/Organizzatori
lorenzo.carlucci@uniroma1.it