Skip to main content

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

New project and new positions


I am looking for a postdoc and PhD student to join me in the autumn of 2024 to work on the EPSRC-funded project “Promise Constraint Satisfaction Problems: Structure and Complexity“. The postdoc position is for 3 years, the closing date for applications is 31 March. The detailed advert (and link to apply) for the postdoc position is here. Please contact me by email for informal inquiries.

The PhD studentship is for 3.5 years and available only to home students. It 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 deadline for applications is 31 March.

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

Another postdoc position and another PhD studentship, both associated with this project, will be available later, to start in the autumn of 2025.

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.