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

New project and new positions

I am looking for two PhD students to join me to work on the EPSRC-funded project “Promise Constraint Satisfaction Problems: Structure and Complexity“.

The PhD studentships are for 3.5 years each and available only to home students. Each studentship includes (home) tuition fee, a standard UKRI stipend, and a small budget for attending conferences. If interested, please contact me by email before applying. The expected start date is negotiable. Applications should be made via the University’s application portal (the list of documents to submit and the link to the portal can be found here).

If you haven’t done CSP research before, but want to know what it’s like, check out surveys “Polymorphisms, and how to use them” and “An invitation to the promise constraint satisfaction problem“.

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:

Oberwolfach Seminar, 14-19 December, 2025. Oberwolfach, Germany.

Dagstuhl Seminar, 18-23 May, 2025. Schloss Dagstuhl, Germany.

The sixth CWC 23-27 September 2024. Colfosco, Italy.

The first Birmingham CSP meeting, 7-8 May, 2024. Birmingham, UK.

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.