20 citations · 75 across the 44 of their papers we have counts for
4 papers · 2 filters
On the complexity of the model checking problem
Florent Madelaine, Barnaby Martin
The model checking problem for various fragments of first-order logic has attracted much attention over the last two decades: in particular, for the primitive positive and the posi…
Containment, Equivalence and Coreness from CSP to QCSP and beyond
Florent Madelaine, Barnaby Martin
The constraint satisfaction problem (CSP) and its quantified extensions, whether without (QCSP) or with disjunction (QCSP_or), correspond naturally to the model checking problem fo…
Parameterized Resolution with bounded conjunction
Stefan Dantchev, Barnaby Martin
We provide separations between the parameterized versions of Res(1) (Resolution) and Res(2). Using a different set of parameterized contradictions, we also separate the parameteriz…
Parameterized Proof Complexity and W[1]
Barnaby Martin
We initiate a program of parameterized proof complexity that aims to provide evidence that FPT is different from W[1]. A similar program already exists for the classes W[2] and W[S…