We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science


Professor Andrei Krokhin, MSc, PhD

Personal web page

Telephone: +44 (0) 191 33 41743
Room number: E372

(email at


Personal webpage

I received PhD in Mathematics from Ural State University, Ekaterinburg, Russia. In 1994-2000, I worked as Assistant Professor in the Department of Mathematics and Mechanics, Ural State University. In 2000-2002 I have been an RA at the Oxford University Computing Laboratory, and after that I worked for two years as Lecturer in Computer Science at Warwick University. I have been at Durham since September 2004, first as Reader and since 2011 as Chair in Computer Science.

Indicators of Esteem

  • 2006: EPSRC Advanced Research Fellowship: Obtained a prestigious Advanced Research Fellowship from the EPSRC, which allow me to concentrate solely on research for five years (2005-2010).
  • 2006: Principal organizer of an international workshop in Oxford: I am the principal organizer of the international workshop "Mathematics of Constraint Satisfaction: Algebra, Logic, and Graph Theory" held in March 2006 in Oxford. I arranged a programme of 25 lectures given by world-leading specialist in the area. There were more than 80 participants in the workshop.
  • 2003: Invited series of lectures at a NATO ASI summer school, University of Montreal: I gave an invited series of four lectures on the topic "The complexity of constraint satisfaction: an algebraic approach" at the NATO ASI Summer School on Automata, Semigroups and Universal Algebra at the University of Montreal, Canada, July 2003.
  • 2003: Plenary speaker at ISMVL 2003: I gave an invited plenary lecture at the 33rd International Symposium on Multiple-Valued Logic (ISMVL 2003) in Tokyo, Japan, in May 2003.

Research Groups

  • Algorithms and Complexity

Research Interests

  • Combinatorics of graphs and ordered sets
  • Computational complexity
  • Homomorphism problems
  • Mathematics of constraint satisfaction
  • Universal algebra and logic in computer science

Selected Publications

Show all publications

Selected Grants

  • 2006: International Workshop on Mathematics of Constraint Satisfaction: Algebra, Logic, and Graph Theory
  • 2005: Combining Approaches in Classifying Complexity of Constraints
  • 2005: Constraint Satisfaction Problems: Complexity and Approximability (EPSRC Advanced Research Fellowship)
  • 2004: Complexity of Constraint Optimisation on ordered Domains: An initial Study
  • 2001: Algebraic Structural Methods and Complexity of Constraint Satisfaction