Skip to main content
AffiliationRoom numberTelephone
Professor in the Department of Computer ScienceMCS 2012+44 (0) 191 33 41743


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.

Research interests

  • mathematics of constraint satisfaction
  • computational complexity
  • homomorphism problems
  • universal algebra and logic in computer science
  • combinatorics of graphs and ordered sets

Research groups

  • Algorithms and Complexity

Esteem Indicators

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


Authored book

  • Krokhin, A. & Zivny, S. (2017). The Constraint Satisfaction Problem: Complexity and Approximability. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.

Chapter in book

Conference Paper

Conference Proceeding

  • Krokhin, A. & Larose, B. (2005). Maximum constraint satisfaction on diamonds. 11th International Conference on Principles and Practice of Constraint Programming {(CP'05), Springer Verlag.

Journal Article