Bounded-depth Frege lower bounds for weaker pigeonhole principles

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

Bounded-depth Frege lower bounds for weaker pigeonhole principles

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

Research output: Contribution to journal › Conference article › peer-review

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 language	English (US)
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

All Science Journal Classification (ASJC) codes

Hardware and Architecture

Cite this

@article{175c7591d58b437bb48e40b224ea3f8b,

title = "Bounded-depth Frege lower bounds for weaker pigeonhole principles",

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.",

author = "Josh Buresh-Oppenheim and Paul Beame and Toniann Pitassi and Ran Raz and Ashish Sabharwal",

year = "2002",

language = "English (US)",

pages = "583--592",

journal = "Annual Symposium on Foundations of Computer Science - Proceedings",

issn = "0272-5428",

note = "The 34rd Annual IEEE Symposium on Foundations of Computer Science ; Conference date: 16-11-2002 Through 19-11-2002",

}

TY - JOUR

T1 - Bounded-depth Frege lower bounds for weaker pigeonhole principles

AU - Buresh-Oppenheim, Josh

AU - Beame, Paul

AU - Pitassi, Toniann

AU - Raz, Ran

AU - Sabharwal, Ashish

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0036949058

UR - https://www.scopus.com/pages/publications/0036949058#tab=citedBy

M3 - Conference article

AN - SCOPUS:0036949058

SN - 0272-5428

SP - 583

EP - 592

JO - Annual Symposium on Foundations of Computer Science - Proceedings

JF - Annual Symposium on Foundations of Computer Science - Proceedings

T2 - The 34rd Annual IEEE Symposium on Foundations of Computer Science

Y2 - 16 November 2002 through 19 November 2002

ER -

Bounded-depth Frege lower bounds for weaker pigeonhole principles

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this