Skip to content

SAS

Seminar

Strong Lower Bounds for Constant-Depth Frege Imply Lower Bounds for Frege

Santhanam, R (University of Edinburgh)
Wednesday 28 March 2012, 09:00-10:00

Seminar Room 1, Newton Institute

Abstract

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.

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧