All reports by Author Barnaby Martin:

__
TR21-022
| 20th February 2021
__

Stefan Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin#### Depth lower bounds in Stabbing Planes for combinatorial principles

Revisions: 1

__
TR18-165
| 20th September 2018
__

Stefan Dantchev, Nicola Galesi, Barnaby Martin#### Resolution and the binary encoding of combinatorial principles

__
TR18-024
| 1st February 2018
__

Olaf Beyersdorff, Judith Clymo, Stefan Dantchev, Barnaby Martin#### The Riis Complexity Gap for QBF Resolution

__
TR07-001
| 19th November 2006
__

Stefan S. Dantchev, Barnaby Martin, Stefan Szeider#### Parameterized Proof Complexity: a Complexity Gap for Parameterized Tree-like Resolution

Revisions: 2

Stefan Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin

We prove logarithmic depth lower bounds in Stabbing Planes for the classes of combinatorial principles known as the Pigeonhole principle and the Tseitin contradictions. The depth lower bounds are new, obtained by giving almost linear length lower bounds which do not depend on the bit-size of the inequalities and in ... more >>>

Stefan Dantchev, Nicola Galesi, Barnaby Martin

We investigate the size complexity of proofs in $RES(s)$ -- an extension of Resolution working on $s$-DNFs instead of clauses -- for families of contradictions given in the {\em unusual binary} encoding. A motivation of our work is size lower bounds of refutations in Resolution for families of contradictions in ... more >>>

Olaf Beyersdorff, Judith Clymo, Stefan Dantchev, Barnaby Martin

We give an analogue of the Riis Complexity Gap Theorem for Quanti fied Boolean Formulas (QBFs). Every fi rst-order sentence $\phi$ without finite models gives rise to a sequence of QBFs whose minimal refutations in tree-like Q-Resolution are either of polynomial size (if $\phi$ has no models) or at least ... more >>>

Stefan S. Dantchev, Barnaby Martin, Stefan Szeider

We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional formula cannot be satisfied by a truth assignment that sets at most k variables to true, considering k as the parameter. One could separate the ... more >>>