# Barnaby Martin

According to our database

Collaborative distances:

^{1}, Barnaby Martin authored at least 55 papers between 2005 and 2018.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2018

On the Complexity of the Model Checking Problem.

SIAM J. Comput., 2018

Discrete Temporal Constraint Satisfaction Problems.

J. ACM, 2018

Resolution and the binary encoding of combinatorial principles.

Electronic Colloquium on Computational Complexity (ECCC), 2018

The Riis Complexity Gap for QBF Resolution.

Electronic Colloquium on Computational Complexity (ECCC), 2018

Surjective H-Colouring over Reflexive Digraphs.

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

Consistency for Counting Quantifiers.

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

The Complexity of Disjunctive Linear Diophantine Constraints.

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Classification Transfer for Qualitative Reasoning Problems.

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

Disconnected Cuts in Claw-free Graphs.

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2017

Quantified Constraint Satisfaction Problem on Semicomplete Digraphs.

ACM Trans. Comput. Log., 2017

The packing chromatic number of the infinite square lattice is between 13 and 15.

Discrete Applied Mathematics, 2017

The Complexity of Quantified Constraints Using the Algebraic Formulation.

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

Quantified Constraints in Twenty Seventeen.

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

Surjective H-Colouring: New Hardness Results.

Proceedings of the Unveiling Dynamics and Complexity, 2017

2016

Distance constraint satisfaction problems.

Inf. Comput., 2016

Report on BCTCS 2015.

Bulletin of the EATCS, 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

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

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 surjective homomorphism problems - a survey.

Discrete Applied Mathematics, 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

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.

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

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

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

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