Skip to main content
Overview
Affiliations
AffiliationTelephone
Professor in the Department of Computer Science

Biography

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

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

Esteem Indicators

  • 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.
  • 2006: EPSRC Advanced Research Fellowship: Obtained a prestigious Advanced ResearchFellowship from the EPSRC, which allow meto concentrate solely on research for five years (2005-2010).
  • 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.
  • 2003: Invited series of lectures at a NATO ASI summer school, University of Montreal: I gave an invited series of four lectureson 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.

Publications

Authored book

Chapter in book

  • Polymorphisms, and how to use them
    Barto, L., Krokhin, A., & Willard, R. (2017). Polymorphisms, and how to use them. In A. Krokhin, & S. Živný (Eds.), The constraint satisfaction problem : complexity and approximability (1-44). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/dfu.vol7.15301.1
  • The complexity of Valued CSPs
    Krokhin, A., & Živný, S. (2017). The complexity of Valued CSPs. In A. Krokhin, & S. Živný (Eds.), The constraint satisfaction problem : complexity and approximability (233-266). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/dfu.vol7.15301.9
  • Towards a Characterization of Constant-Factor Approximable Min CSPs
    Dalmau, V., Krokhin, A., & Manokaran, R. (2015). Towards a Characterization of Constant-Factor Approximable Min CSPs. In P. Indyk (Ed.), Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms : San Diego, California, USA, January 4-6, 2015 (847-857). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973730.58
  • Dualities for constraint satisfaction problems
    Bulatov, A., Krokhin, A., & Larose, B. (2008). Dualities for constraint satisfaction problems. In N. Creignou, P. Kolaitis, & H. Vollmer (Eds.), Complexity of constraints : an overview of current research themes (93-124). Springer Verlag. https://doi.org/10.1007/978-3-540-92800-3_5
  • The complexity of constraint satisfaction: an algebraic approach
    Krokhin, A., Bulatov, A., & Jeavons, P. (2005). The complexity of constraint satisfaction: an algebraic approach. In V. B. Kudryavtsev, & I. G. Rosenberg (Eds.), Structural theory of automata, semigroups, and universal algebra (181-213). Springer Netherlands. https://doi.org/10.1007/1-4020-3817-8_8

Conference Paper

Journal Article

Supervision students