Staff profile

I am an Associate Professor at Durham University in the Algorithms and Complexity Group (ACiD) within the Department of Computer Science. I was previously a lecturer in the Foundations of Computing Group at Middlesex University. Before my permanent appointments I undertook a number of post-doctoral positions in Durham and Paris.

My interests include Complexity Theory in general (Proof Complexity as well as Computational Complexity); Finite Model Theory; and the links between logic and complexity. I am mostly working now on forms of Constraint Satisfaction Problem, Proof Complexity and Algorithmic Graph Theory.

• ACiD: Algorithms and Complexity

Conference Paper

• Berthe, G., Martin, B., Paulusma, D. & Smith, S. (2022), The Complexity of L(p,q)-Edge-Labelling, in Mutzel, Petra, Rahman, Md. Saidur & Slamin eds, Lecture Notes in Computer Science 13174: The 15th International Conference and Workshops on Algorithms and Computation (WALCOM 2021). University of Jember, East Java, Springer, Cham, 175-186.
• Martin, B., Paulusma, D. & Smith, S. (2021), Colouring graphs of bounded diameter in the absence of small cycles, in Calamoneri, Tiziana & Corò, Federico eds, Lecture Notes in Computer Science 12701: CIAC 2021. Virtual Event, Springer, 367-380.
• Dantchev, Stefan Ghani, Abdul & Martin, Barnaby (2020), Sherali-Adams and the binary encoding of combinatorial principles, in Kohayakawa, Yoshiharu & Miyazawa, Flávio Keidi eds, Latin American Symposium on Theoretical Informatics 12118: LATIN 2020. São Paulo, Brazil, 336-347.
• Zhuk, Dmitriy & Martin, Barnaby (2020), QCSP monsters and the demise of the chen conjecture, in Makarychev, Konstantin, Makarychev, Yury, Tulsiani, Madhur, Kamath, Gautam & Chuzhoy, Julia eds, 52nd Annual ACM SIGACT Symposium on Theory of Computing. Chicago, Association for Computing Machinery, New York, 91-104.
• Dantchev, Stefan, Galesi, Nicola & Martin, Barnaby (2019), Resolution and the binary encoding of combinatorial principles, in Shpilka, Amir eds, Leibniz International Proceedings in Informatics (LIPIcs) 137: Computational Complexity Conference. New Brunswick, New Jersey, USA, Dagstuhl Publishing, Saarbrücken/Wadern, 6:1–6:25.
• Larose, B., Martin, B. & Paulusma, D. (2018), Surjective H-Colouring over Reflexive Digraphs, in Niedermeier, Rolf & Vallée, Brigitte eds, Leibniz International Proceedings in Informatics (LIPIcs) 96: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Caen, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 49:1-49:14.
• Bodirsky, Manuel, Mamino, Marcello, Martin, Barnaby & Mottet, Antoine (2018), The complexity of disjunctive linear Diophantine constraints, in Potapov, Igor, Spirakis, Paul & Worrell, James eds, Leibniz International Proceedings in Informatics (LIPIcs) 117: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Liverpool, UK, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Dagstuhl, Germany, 33:1--33:16.
• Bodirsky, Manuel, Jonsson, Peter, Martin, Barnaby & Mottet, Antoine (2018), Classification Transfer for Qualitative Reasoning Problems, in Lang, Jérôme eds, IJCAI-ECAI 2018, the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence. Stockholm, Sweden, International Joint Conferences on Artificial Intelligence Organization, 1256-1262.
• Martin, B., Paulusma, D. & van Leeuwen, E.J. (2018), Disconnected Cuts in Claw-free Graphs, in Azar, Yossi, Bast, Hannah & Herman, Grzegorz eds, Leibniz International Proceedings in Informatics (LIPIcs) 112: 26th Annual European Symposium on Algorithms (ESA 2018). Helsinki, Finland., Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Dagstuhl, Germany, 61:1--61:14.
• Madelaine, Florent & Martin, Barnaby (2018), Consistency for counting quantifiers, in Potapov, Igor, Spirakis, Paul & Worrell, James eds, Leibniz International Proceedings in Informatics (LIPIcs) 117: 43rd International Symposium on Mathematical Foundations of Computer Science. Liverpool, UK, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Dagstuhl, Germany, 11:1--11:13.
• Carvalho, Catarina, Martin, Barnaby & Zhuk, Dmitry (2017), The complexity of quantified constraints using the algebraic formulation, in Larsen, Kim G. Bodlaender, Hans L. & Raskin, Jean-Francois eds, Leibniz International Proceedings in Informatics (LIPIcs) 83: Mathematical Foundation of Computer Science. Aalborg, Denmark, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 27.
• Bodirsky, Manuel, Martin, Barnaby, Pinsker, Michael & Pongrácz, András (2016), Constraint Satisfaction Problems for Reducts of Homogeneous Graphs, in Chatzigiannakis, Ioannis, Mitzenmacher, Michael, Rabani, Yuval & Sangiorgi, Davide eds, LIPIcs - Leibniz International Porceedings in Informatics 55: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy. Rome, Schloss Dagstuhl, Leibniz-Zentrum für Informatik, Dagstuhl, 119:1-119:14.
• Carvalho, Catarina, Madelaine, Florent R. & Martin, Barnaby (2015), From Complexity to Algebra and Back: Digraph Classes, Collapsibility, and the PGP, 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015. Kyoto, Japan, IEEE, Piscataway, NJ, 462-474.
• Bodirsky, Manuel, Martin, Barnaby & Mottet, Antoine (2015), Constraint Satisfaction Problems over the Integers with Successor, in Halldórsson, Magnús M., Iwama, Kazuo, Kobayashi, Naoki & Speckmann, Bettina eds, Lecture Notes in Computer Science, 9134 Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I. Kyoto, Japan, Springer, Berlin, 256-267.

Journal Article

• Berthe, Gaétan, Martin, Barnaby, Paulusma, Daniël & Smith, Siani (2023). The Complexity of L(p, q)-Edge-Labelling. Algorithmica
• Martin, Barnaby, Paulusma, Daniël, Smith, Siani & van Leeuwen, Erik Jan (2023). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. Algorithmica
• Carvalho, Catarina, Madelaine, Florent, Martin, Barnaby & Zhuk, Dmitriy (2023). The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation. ACM Transactions on Computational Logic 24(1): 5, 1–26.
• Carvalho, Catarina & Martin, Barnaby (2022). The lattice and semigroup structure of multipermutations. International Journal of Algebra and Computation 32(2): 211-235.
• Bodirsky, Manuel, Martin, Barnaby, Pinsker, Michael & Pongracz, Andras (2019). Constraint satisfaction problems for reducts of homogeneous graphs. SIAM Journal on Computing 48(4): 1224-1264.
• Larose, B., Martin, B. & Paulusma, D. (2018). Surjective H-Colouring over reflexive digraphs. ACM Transactions on Computation Theory 11(1): 3.
• Madelaine, Florent R. & Martin, Barnaby D. (2018). On the Complexity of the Model Checking Problem. SIAM Journal on Computing 47(3): 769-797.
• Bodirsky, Manuel, Martin, Barnaby & Mottet, Antoine (2018). Discrete Temporal Constraint Satisfaction Problems. Journal of the ACM 65(2): 9.
• Glaßer, Christian, Jonsson, Peter & Martin, Barnaby (2017). Circuit Satisfiability and Constraint Satisfaction around Skolem Arithmetic. Theoretical Computer Science 703: 18-36.
• Martin, Barnaby, Raimondi, Franco, Chen, Taolue & Martin, Jos (2017). The packing chromatic number of the infinite square lattice is between 13 and 15. Discrete Applied Mathematics 225: 136-142.
• Đapić, Petar, Marković, Petar & Martin, Barnaby (2017). Quantified Constraint Satisfaction Problem on semicomplete digraphs. ACM Transactions on Computational Logic 18(1): 2.
• Martin, Barnaby, Pongrácz, András & Wrona, Michał (2017). The complexity of counting quantifiers on equality languages. Theoretical Computer Science 670: 56-67.
• Dantchev, Stefan & Martin, Barnaby (2013). Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems. Computational Complexity 22(1): 191-213.
• Dantchev, Stefan, Martin, Barnaby & Szeider, Stefan (2011). Parameterized Proof Complexity. Computational Complexity 20(1): 51-85.