Andrei Krokhin

I am a Professor at the Department of Computer Science, Durham University.

I am a member of the Algorithms and Complexity Research Group.

Contact

Office: MCS 2012
Phone: +44 (0) 191 334 1743
E-mail: andrei.krokhin at durham.ac.uk

Teaching

I teach L3 Computational Complexity in academic year 2023-24.

Research

My research interests are in the study of mathematical and algorithmic aspects of the constraint satisfaction problem (CSP), often motivated by classification questions about the computational complexity of the CSP.
The most striking feature of this research direction is that, despite computational aspects being its primary motivation, it influences and is influenced by many branches of mathematics, including universal algebra and clone theory (which was my main research interest prior to 2000), topology and category theory, graph theory and combinatorics, logic and finite model theory, group theory and classical model theory, mathematical programming and combinatorial optimisation.
Publications
Tutorial videos
Simons Institute talk recording

Meetings related to Mathematics of Constraint Satisfaction:

The fifth CWC 18-22 September 2023. Weissensee, Austria

The fourth CWC 18-24 September 2022. Molveno, Italy

The Constraint Satisfaction Problem: Complexity and Approximability
Dagstuhl Seminar, 15-20 May, 2022. Schloss Dagstuhl, Germany.

Mathematics of Constraint Satisfaction.
Durham Symposium, 5-9 July, 2021. Durham University, UK.
CANCELLED DUE TO COVID-19.

Homogeneous Structures: Model Theory meets Universal Algebra
Oberwolfach Seminar, 3-9 January, 2021. Oberwolfach, Germany.

The Constraint Satisfaction Problem: Complexity and Approximability
Dagstuhl Seminar, 3-8 June, 2018. Schloss Dagstuhl, Germany.

{Symmetry, Logic, Computation}
Workshop, 7-10 November, 2016. Simons Institute, Berkeley, USA.

Structure and Complexity in Universal Algebra
Workshop, 19-30 September, 2016. Vanderbilt University, Nashville, USA.

Counting Complexity and Phase Transitions
Thematic Programme, 11 January – 13 May, 2016. Simons Institute, Berkeley, USA.

The Constraint Satisfaction Problem: Complexity and Approximability
Dagstuhl Seminar, 19-24 July, 2015. Schloss Dagstuhl, Germany.

Algebraic and Model Theoretical Methods in Constraint Satisfaction
Banff Workshop, 23-28 November, 2014. Banff International Research Station, Canada.

General Algebra and Its Applications
International Conference, 15-19 July, 2013. Melbourne, Australia.

The Constraint Satisfaction Problem: Complexity and Approximability
Dagstuhl Seminar, 4-9 November, 2012. Schloss Dagstuhl, Germany.

Mathematical and Algorithmic Aspects of Constraint Satisfaction
Summer Thematic Program, June-August, 2011. Fields Institute of Mathematics, Toronto, Canada.

Tractability
International Workshop, 5-6 July, 2010. Microsoft Research, Cambridge, UK.

Universal Algebra, Complexity, and CSP
International Workshop, 28-29 June, 2010. Lisbon, Portugal.

The Constraint Satisfaction Problem: Complexity and Approximability
Dagstuhl Seminar, 25-30 October, 2009. Schloss Dagstuhl, Germany.

Logic and Algorithms
International Workshop, 21-25 July, 2008. Edinburgh, UK.

Algorithmic Complexity and Universal Algebra
International Conference, 16-20 July, 2007. Szeged, Hungary.

Universal Algebra and the Constraint Satisfaction Problem
International Workshop, 17-20 June, 2007. Nashville, USA.

Complexity of Constraints
Dagstuhl Seminar, 1-6 October, 2006. Schloss Dagstuhl, Germany.

Mathematics of Constraint Satisfaction: Algebra, Logic, and Graph Theory
International Workshop, 20-24 March, 2006. St.Anne’s College,
University of Oxford, UK.