Skip to main content

Staff profile

Overview

Professor Andrei Krokhin

Professor

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. (pp. 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. (pp. 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. (pp. 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. (pp. 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. (pp. 181-213). Springer Netherlands. https://doi.org/10.1007/1-4020-3817-8_8

Conference Paper

  • The complexity of 3-colouring H-colourable graphs
    Krokhin, A., & Oprsal, J. (2020). The complexity of 3-colouring H-colourable graphs. In D. Zuckerman (Ed.), 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS 2019) ; proceedings. (pp. 1227-1239). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/focs.2019.00076
  • Algebraic approach to promise constraint satisfaction
    Bulin, J., Krokhin, A., & Oprsal, J. (2019). Algebraic approach to promise constraint satisfaction. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019). (pp. 602-613). ACM. https://doi.org/10.1145/3313276.3316300
  • Robust algorithms with polynomial loss for near-unanimity CSPs
    Dalmau, V., Kozik, M., Krokhin, A., Makarychev, K., Makarychev, Y., & Oprsal, J. (2017). Robust algorithms with polynomial loss for near-unanimity CSPs. In P. N. Klein (Ed.), Proceedings of the twenty-eighth Annual ACM-SIAM symposium on discrete algorithms. (pp. 340-357). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611974782.22
  • The Complexity of General-Valued CSPs
    Kolmogorov, V., Krokhin, A., & Rolinek, M. (2015). The Complexity of General-Valued CSPs. In 2015 IEEE 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015) : Berkeley, California, USA, 17-20 October 2015 ; proceedings. (pp. 1246-1258). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/focs.2015.80
  • The complexity of the list homomorphism problem for graphs.
    Egri, L., Krokhin, A., Larose, B., & Tesson, P. (2010). The complexity of the list homomorphism problem for graphs. In J. .-Y. Marion & T. Schwentick (Eds.), LIPIcs (pp. 335-346). https://doi.org/10.4230/lipics.stacs.2010.2467
  • Caterpillar duality for constraint satisfaction problems
    Carvalho, C., Dalmau, V., & Krokhin, A. (2008). Caterpillar duality for constraint satisfaction problems. In Twenty-third Annual IEEE Symposium on Logic in Computer Science, 24-27 June 2008, Pittsburgh, PA ; proceedings. (pp. 307-316). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/lics.2008.19
  • Maximum constraint satisfaction on diamonds
    Krokhin, A., & Larose, B. (2005). Maximum constraint satisfaction on diamonds. In P. ~van Beek (Ed.), Lecture Notes in Computer Science (pp. 388-402). Springer Verlag.
  • Supermodularity on chains and complexity of maximum constraint satisfaction
    Deineko, V., Jonsson, P., Klasson, M., & Krokhin, A. (2005). Supermodularity on chains and complexity of maximum constraint satisfaction. In S. Felsner (Ed.), DMTCS Proceedings (pp. 51-56). Discrete Mathematics and Theoretical Computer Science.
  • Identifying efficiently solvable cases of Max CSP
    Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2004). Identifying efficiently solvable cases of Max CSP. In M. Habib & V. Diekert (Eds.), Lecture Notes in Computer Science (pp. 152-163). Springer Verlag.
  • First-Order Definable Retraction Problems for Posets and Reflexive Graphs
    Dalmau, V., Krokhin, A., & Larose, B. (2004). First-Order Definable Retraction Problems for Posets and Reflexive Graphs. In 19th annual IEEE symposium on logic in computer science, LICS’04, 13-17 July 2004, Turku, Finland ; proceedings. (pp. 232-241). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/lics.2004.1319617
  • Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey
    Krokhin, A., Bulatov, A., & Jeavons, P. (2003). Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey. In 33rd international symposium on multiple-valued logic, ISMVL’03, 16-19 May 2003, Meiji University, Tokyo, Japan ; proceedings. (pp. 343-351). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ismvl.2003.1201427
  • Solving order constraints in logarithmic space
    Krokhin, A., & Larose, B. (2003). Solving order constraints in logarithmic space. In H. Alt & M. Habib (Eds.), 20th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2003, 27 February-1 March 1 2003 ; proceedings. (pp. 379-390). Springer Verlag. https://doi.org/10.1007/3-540-36494-3_34
  • A tractable class of soft constraints.
    Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2003). A tractable class of soft constraints (G. Gottlob & T. Walsh, Eds.). Morgan Kaufmann.
  • Quantified constraints: Algorithms and complexity
    Boerner, F., Bulatov, A., Jeavons, P., & Krokhin, A. (2003). Quantified constraints: Algorithms and complexity. In M. Baaz & J. Makowsky (Eds.), Lecture Notes in Computer Science (pp. 58-70). Springer Verlag.
  • Soft constraints: complexity and multimorphisms
    Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2003). Soft constraints: complexity and multimorphisms. In F. Rossi (Ed.), Lecture Notes in Computer Science (pp. 244-258). Springer Verlag.
  • Extending the Point Algebra into the Qualitative Algebra
    Krokhin, A., & Jonsson, P. (2002). Extending the Point Algebra into the Qualitative Algebra (M. Fisher, Ed.). Institute of Electrical and Electronics Engineers.
  • The complexity of constraints on intervals and lengths
    Krokhin, A., Jeavons, P., & Jonsson, P. (2002). The complexity of constraints on intervals and lengths. In H. Alt & A. Ferreira (Eds.), Lecture Notes in Computer Science (pp. 443-454). Springer Verlag.
  • A complete classification of complexity in Allen's algebrain the presence of a non-trivial basic relation
    Krokhin, A., Jeavons, P., & Jonsson, P. (2001). A complete classification of complexity in Allen’s algebrain the presence of a non-trivial basic relation (B. Nebel, Ed.). Morgan Kaufmann.
  • The complexity of maximal constraint languages
    Bulatov, A., Krokhin, A., & Jeavons, P. (2001). The complexity of maximal constraint languages. In Proceedings of the 33rd annual ACM symposium on theory of computing. (pp. 667-674). Association for Computing Machinery (ACM). https://doi.org/10.1145/380752.380868
  • On the structure of clone lattices, II
    Bulatov, A., Krokhin, A., Safin, K., Semigrodskikh, A., & Sukhanov, E. (2001). On the structure of clone lattices, II.

Journal Article

Supervision students

Yiming Qiu

Postgraduate Student