معرفی
Dr. Barnaby Martin is an Associate Professor in the Department of Computer Science at Durham University, working within the Algorithms and Complexity Group (ACiD). His research focuses on theoretical computer science, including computational complexity, proof complexity, finite model theory, and constraint satisfaction problems (CSPs), with a particular emphasis on algorithmic graph theory and forbidden subgraph frameworks.
He holds a permanent academic position after prior roles at Middlesex University and post-doctoral positions in Durham and Paris. His work explores the boundary between tractable and intractable computational problems, often investigating how structural graph properties influence complexity.
Key research directions include developing complexity frameworks for problems restricted to subcubic graphs, analyzing quantified constraint satisfaction problems (QCSP), and studying coloring and partitioning problems for H-free graphs. Recent contributions include advancements in Steiner Forest problem complexity, edge subdivision frameworks, and QCSP classifications over reflexive tournaments.
Dr. Martin has supervised postgraduate students Tala Eagling-Vose and Yiming Qiu. His publications span conferences like ISAAC, SWAT, and MFCS, with a strong presence in algorithmic and complexity theory venues. He has contributed to foundational areas such as Sherali-Adams proof systems and the Chen conjecture in QCSP theory.
