# Andrei Krokhin

# 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.