Barnaby Martin

Dr. Barnaby Martin is an Associate Professor in the Department of Computer Science at Durham University, part of the Algorithms and Complexity Group (ACiD). Previously, he held a lectureship at Middlesex University and undertook postdoctoral roles at Durham and Paris institutions.

His research focuses on Complexity Theory, including Proof Complexity and Computational Complexity, as well as Finite Model Theory and links between logic and complexity. Current work emphasizes Constraint Satisfaction Problems (CSP), Proof Complexity, and Algorithmic Graph Theory. His recent publications explore forbidden subgraphs, edge subdivision, Steiner Forest problems, and H-free graphs.

Dr. Martin’s articles often address computational challenges in graph theory and algorithm design, with a recurring theme of analyzing tractability and hardness in specific graph classes. He has collaborated extensively with researchers like Daniel Paulusma, Siani Smith, and others on topics ranging from graph coloring to quantified constraint satisfaction problems.

He supervises postgraduate students Tala Eagling-Vose and Yiming Qiu. His work has been published in venues such as Algorithmica, SIAM Journal on Computing, and ACM Transactions on Computational Logic. His research bridges theoretical computer science and discrete mathematics, contributing to foundational understanding of computational limits in structured domains.