Regular resolution lower bounds for the weak pigeonhole principle

Toniann Pitassi, Ran Raz

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


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 languageEnglish (US)
Pages (from-to)503-524
Number of pages22
Issue number3
StatePublished - 2004
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


Dive into the research topics of 'Regular resolution lower bounds for the weak pigeonhole principle'. Together they form a unique fingerprint.

Cite this