University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Lower Bounds for Frege from Lower Bounds for Constant-Depth Frege

Lower Bounds for Frege from Lower Bounds for Constant-Depth Frege

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Mustapha Amrani.

Semantics and Syntax: A Legacy of Alan Turing

I will discuss a recent result proved with Yuval Filmus and Toni Pitassi: exponential size lower bounds for constant-depth Frege imply superpolynomial size lower bounds for Frege. The proof is constructive in that it shows how to simulate polynomial size Frege proofs for any sequence of tautologies with sub-exponential size proofs in constant-depth Frege. The simulation is tight for tree-like proofs. I will also mention consequences of the result for weak automatizability of constant-depth Frege.

This talk is part of the Isaac Newton Institute Seminar Series series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity