Abstract
We prove a quasi-polynomial lower bound on the size of bounded-depth Frege proofs of the pigeonhole principle PHPnm where m = (1 + 1/polylog n)n. This lower bound qualitatively matches the known quasi-polynomial-size bounded-depth Frege proofs for these principles. Our technique, which uses a switching lemma argument like other lower bounds for bounded-depth Frege proofs, is novel in that the tautology to which this switching lemma is applied remains random throughout the argument.
Original language | American English |
---|---|
Pages (from-to) | 583-592 |
Number of pages | 10 |
Journal | Annual Symposium on Foundations of Computer Science - Proceedings |
State | Published - 2002 |
Externally published | Yes |
Event | The 34rd Annual IEEE Symposium on Foundations of Computer Science - Vancouver, BC, Canada Duration: Nov 16 2002 → Nov 19 2002 |
ASJC Scopus subject areas
- Hardware and Architecture