Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-116 | 29th August 2013 23:19

Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle

RSS-Feed




TR13-116
Authors: Albert Atserias, Moritz Müller, Sergi Oliva
Publication: 30th August 2013 14:20
Downloads: 2921
Keywords: 


Abstract:

The relativized weak pigeonhole principle states that if at least $2n$ out of $n^2$ pigeons fly into $n$ holes, then some hole must be doubly occupied. We prove that every DNF-refutation of the CNF encoding of this principle requires size $2^{(\log n)^{3/2-\epsilon}}$ for every $\epsilon > 0$ and every sufficiently large $n$. By reducing it to the standard weak pigeonhole principle with $2n$ pigeons and $n$ holes, we also show that this lower bound is essentially tight in that there exist DNF-refutations of size $2^{(\log n)^{O(1)}}$ even in R($\log$). For the lower bound proof we need to discuss the existence of unbalanced low-degree bipartite expanders satisfying a certain robustness condition.



ISSN 1433-8092 | Imprint