Regular resolution lower bounds for the weak pigeonhole principle

Toniann Pitassi, Ran Raz

Research output: Contribution to journalArticlepeer-review

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

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

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

Cite this