Bounded-depth frege lower bounds for weaker pigeonhole principles

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

doi:10.1137/S0097539703433146

Bounded-depth frege lower bounds for weaker pigeonhole principles

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

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	261-276
Number of pages	16
Journal	SIAM Journal on Computing
Volume	34
Issue number	2
DOIs	https://doi.org/10.1137/S0097539703433146
State	Published - 2005
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Keywords

Pigeonhole principle
Propositional proof complexity

Access to Document

10.1137/S0097539703433146

Cite this

@article{cc76a5ec41664921bc4f1ba9e38201cb,

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

keywords = "Pigeonhole principle, Propositional proof complexity",

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

year = "2005",

doi = "10.1137/S0097539703433146",

language = "English (US)",

volume = "34",

pages = "261--276",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

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

AU - Buresh-Oppenheim, Joshua

AU - Beame, Paul

AU - Pitassi, Toniann

AU - Raz, Ran

AU - Sabharwal, Ashish

PY - 2005

Y1 - 2005

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

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

KW - Pigeonhole principle

KW - Propositional proof complexity

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

UR - https://www.scopus.com/inward/citedby.url?scp=18444366518&partnerID=8YFLogxK

U2 - 10.1137/S0097539703433146

DO - 10.1137/S0097539703433146

M3 - Article

AN - SCOPUS:18444366518

SN - 0097-5397

VL - 34

SP - 261

EP - 276

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 2

ER -

Bounded-depth frege lower bounds for weaker pigeonhole principles

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this