Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with bounded-depth Frege:
TR10-197 | 14th December 2010
Albert Atserias, Elitza Maneva

Mean-payoff games and propositional proofs

We associate a CNF-formula to every instance of the mean-payoff game problem in such a way that if the value of the game is non-negative the formula is satisfiable, and if the value of the game is negative the formula has a polynomial-size refutation in $\Sigma_2$-Frege (i.e.~DNF-resolution). This reduces mean-payoff ... more >>>

TR10-198 | 13th December 2010
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander Razborov

Parameterized Bounded-Depth Frege is Not Optimal

A general framework for parameterized proof complexity was introduced by Dantchev, Martin, and Szeider (FOCS'07). In that framework the parameterized version of any proof system is not fpt-bounded for some technical reasons, but we remark that this question becomes much more interesting if we restrict ourselves to those parameterized contradictions ... more >>>

TR13-116 | 29th August 2013
Albert Atserias, Moritz Müller, Sergi Oliva

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

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

ISSN 1433-8092 | Imprint