Simplified Lower Bounds for Propositional Proofs
Xudong Fu, Alasdair Urquhart · Notre Dame Journal of Formal Logic · 1996
This article presents a simplified proof of the result that bounded depth propositional proofs of the pigeonhole principle are exponentially large. The proof uses the new techniques for proving switching lemmas developed by Razborov and Beame. A similar result is also proved for some examples based on graphs.