Bounded-depth frege lower bounds for weaker pigeonhole principles

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

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

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
Volume34
Issue number2
DOIs
StatePublished - May 23 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Pigeonhole principle
  • Propositional proof complexity

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

  • Cite this