Lower Bounds for Bounded-Depth Frege Proofs via Buss-Pudlack Games
Eli Ben‐Sasson, Prahladh Harsha · Electronic colloquium on computational complexity · 2003
We present a simple proof of the bounded-depth Frege lower bounds of Pitassi et. al. and Kraj´ˇ cek et. al. for the pigeonhole principle. Our method uses the interpretation of proofs as two player games