Bounded-depth Frege lower bounds for weaker pigeonhole principles

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

Research output: Contribution to journalConference article

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 languageEnglish (US)
Pages (from-to)583-592
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Dec 1 2002
Externally publishedYes
EventThe 34rd Annual IEEE Symposium on Foundations of Computer Science - Vancouver, BC, Canada
Duration: Nov 16 2002Nov 19 2002

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

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

Cite this