# Barnaby Martin

According to our database

^{1}, Barnaby Martin## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2017

Quantified Constraint Satisfaction Problem on Semicomplete Digraphs.

ACM Trans. Comput. Log., 2017

The complexity of counting quantifiers on equality languages.

Theor. Comput. Sci., 2017

Surjective H-Colouring: New Hardness Results.

CoRR, 2017

The complexity of quantified constraints.

CoRR, 2017

Quantified Constraints in Twenty Seventeen.

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

2016

Distance constraint satisfaction problems.

Inf. Comput., 2016

Report on BCTCS 2015.

Bulletin of the EATCS, 2016

On the Chen Conjecture regarding the complexity of QCSPs.

CoRR, 2016

Constraint satisfaction problems for reducts of homogeneous graphs.

CoRR, 2016

Constraint Satisfaction Problems for Reducts of Homogeneous Graphs.

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

The Complexity of Counting Quantifiers on Equality Languages.

Proceedings of the Pursuit of the Universal - 12th Conference on Computability in Europe, 2016

Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic.

Proceedings of the Pursuit of the Universal - 12th Conference on Computability in Europe, 2016

2015

Constraint Satisfaction with Counting Quantifiers.

SIAM J. Discrete Math., 2015

The computational complexity of disconnected cut and 2

_{K2}-partition.
J. Comb. Theory, Ser. B, 2015

Switchability and collapsibility of Gap Algebras.

CoRR, 2015

The packing chromatic number of the infinite square lattice is less than or equal to 16.

CoRR, 2015

Constraint Satisfaction Problems around Skolem Arithmetic.

CoRR, 2015

Quantified Constraints and Containment Problems.

Logical Methods in Computer Science, 2015

From complexity to algebra and back: digraph classes, collapsibility and the PGP.

CoRR, 2015

Constraint Satisfaction Problems over the Integers with Successor.

CoRR, 2015

From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP.

Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

Constraint Satisfaction Problems over the Integers with Successor.

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

First-Order Queries on Finite Abelian Groups.

Proceedings of the 24th EACSL Annual Conference on Computer Science Logic, 2015

2014

Relativization makes contradictions harder for Resolution.

Ann. Pure Appl. Logic, 2014

QCSP on Semicomplete Digraphs.

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Constraint Satisfaction with Counting Quantifiers 2.

Proceedings of the Computer Science - Theory and Applications, 2014

2013

Relativisation makes contradictions harder for Resolution

CoRR, 2013

QCSP on partially reflexive cycles - the wavy line of tractability

CoRR, 2013

Constraint Satisfaction with Counting Quantifiers 2.

CoRR, 2013

Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems.

Computational Complexity, 2013

QCSP on Partially Reflexive Cycles - The Wavy Line of Tractability.

Proceedings of the Computer Science - Theory and Applications, 2013

Parameterized Resolution with Bounded Conjunction.

Proceedings of the Computer Science - Theory and Applications, 2013

2012

The Complexity of Positive First-Order Logic without Equality.

ACM Trans. Comput. Log., 2012

Cutting Planes and the Parameter Cutwidth.

Theory Comput. Syst., 2012

The complexity of surjective homomorphism problems - a survey.

Discrete Applied Mathematics, 2012

On the complexity of the model checking problem

CoRR, 2012

Containment, Equivalence and Coreness from CSP to QCSP and beyond

CoRR, 2012

Parameterized Resolution with bounded conjunction

CoRR, 2012

Finding vertex-surjective graph homomorphisms

CoRR, 2012

Parameterized Proof Complexity and W[1]

CoRR, 2012

The limits of tractability in Resolution-based propositional proof systems.

Ann. Pure Appl. Logic, 2012

Finding vertex-surjective graph homomorphisms.

Acta Inf., 2012

Constraint Satisfaction with Counting Quantifiers.

Proceedings of the Computer Science - Theory and Applications, 2012

Finding Vertex-Surjective Graph Homomorphisms.

Proceedings of the Computer Science - Theory and Applications, 2012

Containment, Equivalence and Coreness from CSP to QCSP and Beyond.

Proceedings of the Principles and Practice of Constraint Programming, 2012

2011

Low-level dichotomy for quantified constraint satisfaction problems.

Inf. Process. Lett., 2011

Constraint Satisfaction with Counting Quantifiers

CoRR, 2011

The Complexity of Surjective Homomorphism Problems -- a Survey

CoRR, 2011

The Computational Complexity of Disconnected Cut and 2K2-Partition

CoRR, 2011

QCSP on partially reflexive forests

CoRR, 2011

Low-level dichotomy for Quantified Constraint Satisfaction Problems

CoRR, 2011

Parameterized Proof Complexity.

Computational Complexity, 2011

A Tetrachotomy for Positive First-Order Logic without Equality.

Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, 2011

The Computational Complexity of Disconnected Cut and 2K 2-Partition.

Proceedings of the Principles and Practice of Constraint Programming - CP 2011, 2011

QCSP on Partially Reflexive Forests.

Proceedings of the Principles and Practice of Constraint Programming - CP 2011, 2011

2010

Distance Constraint Satisfaction Problems

CoRR, 2010

The complexity of positive first-order logic without equality

CoRR, 2010

Distance Constraint Satisfaction Problems.

Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction.

Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, 2010

The Complexity of Positive First-Order Logic without Equality II: The Four-Element Case.

Proceedings of the Computer Science Logic, 24th International Workshop, 2010

The Lattice Structure of Sets of Surjective Hyper-Operations.

Proceedings of the Principles and Practice of Constraint Programming - CP 2010, 2010

The Limits of Tractability in Resolution-Based Propositional Proof Systems.

Proceedings of the Programs, Proofs, Processes, 6th Conference on Computability in Europe, 2010

2009

Tight rank lower bounds for the Sherali-Adams proof system.

Theor. Comput. Sci., 2009

On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction

Logical Methods in Computer Science, 2009

The Complexity of Positive First-order Logic without Equality.

Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, 2009

The complexity of positive first-order logic without equality II: The four-element case.

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 25.10., 2009

Cutting Planes and the Parameter Cutwidth.

Proceedings of the Mathematical Theory and Computational Practice, 2009

2008

Model Checking Positive Equality-free FO: Boolean Structures and Digraphs of Size Three

CoRR, 2008

Quantified Constraints and Containment Problems.

Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, 2008

First-Order Model Checking Problems Parameterized by the Model.

Proceedings of the Logic and Theory of Algorithms, 2008

2007

Parameterized Proof Complexity: a Complexity Gap for Parameterized Tree-like Resolution.

Electronic Colloquium on Computational Complexity (ECCC), 2007

On the Complexity of a Derivative Chess Problem

CoRR, 2007

Parameterized Proof Complexity.

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Hierarchies in Fragments of Monadic Strict NP.

Proceedings of the Computation and Logic in the Real World, 2007

2006

Dichotomies and Duality in First-order Model Checking Problems

CoRR, 2006

Towards a Trichotomy for Quantified

*H*-Coloring.
Proceedings of the Logical Approaches to Computational Barriers, 2006

2005

Logic, computation and constraint satisfaction.

PhD thesis, 2005