Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-055 | 26th July 2001 00:00

Improved Resolution Lower Bounds for the Weak Pigeonhole Principle

RSS-Feed




TR01-055
Authors: Alexander Razborov
Publication: 26th July 2001 16:49
Downloads: 2348
Keywords: 


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$).



ISSN 1433-8092 | Imprint