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

