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-075 | 2nd November 2001 00:00

Resolution Lower Bounds for the Weak Functional Pigeonhole Principle

RSS-Feed




TR01-075
Authors: Alexander Razborov
Publication: 2nd November 2001 11:49
Downloads: 1364
Keywords: 


Abstract:

We show that every resolution proof of the {\em functional} version
$FPHP^m_n$ of the pigeonhole principle (in which one pigeon may not split
between several holes) must have size $\exp\of{\Omega\of{\frac n{(\log
m)^2}}}$. This implies an $\exp\of{\Omega(n^{1/3})}$ bound when the number
of pigeons $m$ is arbitrary.



ISSN 1433-8092 | Imprint