Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > WEAK PIGEONHOLE PRINCIPLE:
Reports tagged with Weak pigeonhole principle:
TR01-055 | 26th July 2001
Alexander Razborov

Improved Resolution Lower Bounds for the Weak Pigeonhole Principle

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 ... more >>>




ISSN 1433-8092 | Imprint