Bounded-depth frege lower bounds for weaker pigeonhole principles

Joshua Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


We prove a quasi-polynomial lower bound on the size of bounded-depth Frege proofs of the pigeonhole principle PHP n m 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 languageEnglish (US)
Pages (from-to)261-276
Number of pages16
JournalSIAM Journal on Computing
Issue number2
StatePublished - 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


  • Pigeonhole principle
  • Propositional proof complexity


Dive into the research topics of 'Bounded-depth frege lower bounds for weaker pigeonhole principles'. Together they form a unique fingerprint.

Cite this