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

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

• Santhanam, R (University of Edinburgh)
• Wednesday 28 March 2012, 09:00-10:00
• Seminar Room 1, Newton Institute.

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

This talk has been canceled/deleted

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.

This talk is included in these lists:

This talk is not included in any other list

Note that ex-directory lists are not shown.