All reports by Author Sergi Oliva:

__
TR13-116
| 29th August 2013
__

Albert Atserias, Moritz MÃ¼ller, Sergi Oliva#### Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle

__
TR12-096
| 17th July 2012
__

Albert Atserias, Sergi Oliva#### Bounded-width QBF is PSPACE-complete

Revisions: 3

Albert Atserias, Moritz MÃ¼ller, Sergi Oliva

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

Albert Atserias, Sergi Oliva

Tree-width is a well-studied parameter of structures that measures their similarity to a tree. Many important NP-complete problems, such as Boolean satisfiability (SAT), are tractable on bounded tree-width instances. In this paper we focus on the canonical PSPACE-complete problem QBF, the fully-quantified version of SAT. It was shown by Pan ... more >>>