Regular resolution lower bounds for the weak pigeonhole principle

Toniann Pitassi; Ran Raz

doi:10.1007/s00493-004-0030-y

Regular resolution lower bounds for the weak pigeonhole principle

Toniann Pitassi, Ran Raz

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

8 Scopus citations

Abstract

We prove that any regular resolution proof for the weak pigeon hole principle, with n holes and any number of pigeons, is of length Ω(2 ^n∈), (for some global constant ∈ > 0).

Original language	English (US)
Pages (from-to)	503-524
Number of pages	22
Journal	Combinatorica
Volume	24
Issue number	3
DOIs	https://doi.org/10.1007/s00493-004-0030-y
State	Published - 2004
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s00493-004-0030-y

Cite this

@article{a8345c1a74614c20b528c5f5cfc34b38,

title = "Regular resolution lower bounds for the weak pigeonhole principle",

abstract = "We prove that any regular resolution proof for the weak pigeon hole principle, with n holes and any number of pigeons, is of length Ω(2 n∈), (for some global constant ∈ > 0).",

author = "Toniann Pitassi and Ran Raz",

note = "Funding Information: * Research supported by NSF grant CCR-9820831, US-Israel BSF grant 98-00349, and an NSERC grant. † Research supported by US-Israel BSF grant 98-00349, and NSF grant CCR-9987077.",

year = "2004",

doi = "10.1007/s00493-004-0030-y",

language = "English (US)",

volume = "24",

pages = "503--524",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "3",

}

TY - JOUR

T1 - Regular resolution lower bounds for the weak pigeonhole principle

AU - Pitassi, Toniann

AU - Raz, Ran

N1 - Funding Information: * Research supported by NSF grant CCR-9820831, US-Israel BSF grant 98-00349, and an NSERC grant. † Research supported by US-Israel BSF grant 98-00349, and NSF grant CCR-9987077.

PY - 2004

Y1 - 2004

N2 - We prove that any regular resolution proof for the weak pigeon hole principle, with n holes and any number of pigeons, is of length Ω(2 n∈), (for some global constant ∈ > 0).

AB - We prove that any regular resolution proof for the weak pigeon hole principle, with n holes and any number of pigeons, is of length Ω(2 n∈), (for some global constant ∈ > 0).

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

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

U2 - 10.1007/s00493-004-0030-y

DO - 10.1007/s00493-004-0030-y

M3 - Article

AN - SCOPUS:6344249367

SN - 0209-9683

VL - 24

SP - 503

EP - 524

JO - Combinatorica

JF - Combinatorica

IS - 3

ER -

Regular resolution lower bounds for the weak pigeonhole principle

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this