[Proof Complexity] New paper

[Albert Atserias]

Dear Friends and Colleagues,

We are please to announce the final and improved version of our paper that appeared in the proceedings of CCC 2013 with the title "Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle". Besides improving the writing of the main result and adding some discussion, the final version extends the conference proceedings version by providing an upper bound that shows that the quasipolynomial lower bound of the main result is tight.

URL:
http://www.lsi.upc.edu/~atserias/papers/relativizedwphp/relativizedwphp.pdf

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

Authors: 
Albert Atserias, Moritz Mueller and Sergi Oliva

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 $\Res(\log)$. For the lower bound proof we need to discuss the existence of unbalanced low-degree bipartite expanders satisfying a certain robustness condition.

------------------------------------------------------