All reports by Author Moritz Müller:

__
TR17-144
| 27th September 2017
__

Moritz Müller, Ján Pich#### Feasibly constructive proofs of succinct weak circuit lower bounds

Revisions: 1

__
TR13-116
| 29th August 2013
__

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

__
TR13-113
| 19th August 2013
__

Moritz Müller, Stefan Szeider#### Revisiting Space in Proof Complexity: Treewidth and Pathwidth

__
TR12-018
| 24th February 2012
__

Joerg Flum, Moritz Müller#### Some definitorial suggestions for parameterized proof complexity

Moritz Müller, Ján Pich

We ask for feasibly constructive proofs of known circuit lower bounds for explicit functions on bit strings of length $n$. In 1995 Razborov showed that many can be proved in Cook’s theory $PV_1$, a bounded arithmetic formalizing polynomial time reasoning. He formalized circuit lower bound statements for small $n$ of ... more >>>

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

Moritz Müller, Stefan Szeider

So-called ordered variants of the classical notions of pathwidth and treewidth are introduced and proposed as proof theoretically meaningful complexity measures for the directed acyclic graphs underlying proofs. The ordered pathwidth of a proof is shown to be roughly the same as its formula space. Length-space lower bounds for R(k)-refutations ... more >>>

Joerg Flum, Moritz Müller

We introduce a (new) notion of parameterized proof system. For parameterized versions of standard proof systems such as Extended Frege and Substitution Frege we compare their complexity with respect to parameterized simulations.

more >>>