__
TR01-055 | 26th July 2001 00:00
__

#### Improved Resolution Lower Bounds for the Weak Pigeonhole Principle

**Abstract:**
Recently, Raz established exponential lower bounds on the size

of resolution proofs of the weak pigeonhole principle. We give another

proof of this result which leads to better numerical bounds. Specifically,

we show that every resolution proof of $PHP^m_n$ must have size

$\exp\of{\Omega(n/\log m)^{1/2}}$ which implies an

$\exp\of{\Omega(n^{1/3})}$ bound when the number of pigeons $m$ is

arbitrary.

As a step toward extending this bound to the {\em functional} version of

$PHP^m_n$ (in which one pigeon may not split between several holes), we

introduce one intermediate version (in the form of a $PHP$-oriented

calculus) which, roughly speaking, allows arbitrary ``monotone reasoning''

about the location of an individual pigeon. For this version we prove an

$\exp\of{\Omega(n/\log^2 m)^{1/2}}$ lower bound

($\exp\of{\Omega(n^{1/4})}$ for arbitrary $m$).