Staff profile

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.

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

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

Authored book

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

Chapter in book

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

• 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 (1227-1239). https://doi.org/10.1109/focs.2019.00076
• 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) (602-613). https://doi.org/10.1145/3313276.3316300
• 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 (340-357). https://doi.org/10.1137/1.9781611974782.22
• 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 (1246-1258). https://doi.org/10.1109/focs.2015.80
• Egri, L., Krokhin, A., Larose, B., & Tesson, P. (2010). The complexity of the list homomorphism problem for graphs. In J. -. Marion, & T. Schwentick (Eds.), . https://doi.org/10.4230/lipics.stacs.2010.2467
• 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 (307 -316). https://doi.org/10.1109/lics.2008.19
• Deineko, V., Jonsson, P., Klasson, M., & Krokhin, A. (2005). Supermodularity on chains and complexity of maximum constraint satisfaction. In S. Felsner (Ed.),
• Krokhin, A., & Larose, B. (2005). Maximum constraint satisfaction on diamonds. In P. ~van Beek (Ed.),
• Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2004). Identifying efficiently solvable cases of Max CSP. In M. Habib, & V. Diekert (Eds.),
• 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 (232-241). https://doi.org/10.1109/lics.2004.1319617
• 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 (343-351). https://doi.org/10.1109/ismvl.2003.1201427
• 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 (379-390). https://doi.org/10.1007/3-540-36494-3_34
• Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2003). A tractable class of soft constraints. In G. Gottlob, & T. Walsh (Eds.),
• Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2003). Soft constraints: complexity and multimorphisms. In F. Rossi (Ed.),
• Boerner, F., Bulatov, A., Jeavons, P., & Krokhin, A. (2003). Quantified constraints: Algorithms and complexity. In M. Baaz, & J. Makowsky (Eds.),
• Krokhin, A., & Jonsson, P. (2002). Extending the Point Algebra into the Qualitative Algebra. In M. Fisher (Ed.),
• Krokhin, A., Jeavons, P., & Jonsson, P. (2002). The complexity of constraints on intervals and lengths. In H. Alt, & A. Ferreira (Eds.),
• 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 (667-674). https://doi.org/10.1145/380752.380868
• Krokhin, A., Jeavons, P., & Jonsson, P. (2001). A complete classification of complexity in Allen's algebrain the presence of a non-trivial basic relation. In B. Nebel (Ed.),
• Bulatov, A., Krokhin, A., Safin, K., Semigrodskikh, A., & Sukhanov, E. (2001). On the structure of clone lattices, II.

Journal Article

• Krokhin, A., Opršal, J., Wrochna, M., & Živný, S. (2023). Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing, 52(1), 38-79. https://doi.org/10.1137/20m1378223
• Barto, L., Bulín, J., Krokhin, A., & Opršal, J. (2021). Algebraic Approach to Promise Constraint Satisfaction. Journal of the ACM, 68(4), 1-66. https://doi.org/10.1145/3457606
• Dalmau, V., Kozik, M., Krokhin, A., Makarychev, K., Makarychev, Y., & Oprsal, J. (2019). Robust algorithms with polynomial loss for near-unanimity CSPs. SIAM Journal on Computing, 48(6), 1763-1795. https://doi.org/10.1137/18m1163932
• Dalmau, V., Krokhin, A., & Manokaran, R. (2018). Towards a characterization of constant-factor approximable Finite-Valued CSPs. Journal of Computer and System Sciences, 97, 14-27. https://doi.org/10.1016/j.jcss.2018.03.003
• Cohen, D., Cooper, M., Jeavons, P., Krokhin, A., Powell, R., & Zivny, S. (2017). Binarisation for Valued Constraint Satisfaction Problems. SIAM Journal on Discrete Mathematics, 31(4), 2279-2300. https://doi.org/10.1137/16m1088107
• Kolmogorov, V., Krokhin, A., & Rolínek, M. (2017). The complexity of general-valued CSPs. SIAM Journal on Computing, 46(3), 1087-1110. https://doi.org/10.1137/16m1091836
• Carvalho, C., & Krokhin, A. (2016). On algebras with many symmetric operations. International Journal of Algebra and Computation, 26(05), 1019-1032. https://doi.org/10.1142/s0218196716500429
• Kozik, M., Krokhin, A., Valeriote, M., & Willard, R. (2015). Characterizations of several Maltsev conditions. Algebra Universalis, 73(3), 205-224. https://doi.org/10.1007/s00012-015-0327-2
• Huber, A., & Krokhin, A. (2014). Oracle Tractability of Skew Bisubmodular Functions. SIAM Journal on Discrete Mathematics, 28(4), 1828-1837. https://doi.org/10.1137/130936038
• Jeavons, P., Krokhin, A., & Živný, S. (2014). The Complexity of Valued Constraint Satisfaction. Bulletin of the European Association for Theoretical Computer Science, 113, 21-55
• Huber, A., Krokhin, A., & Powell, R. (2014). Skew Bisubmodularity and Valued CSPs. SIAM Journal on Computing, 43(3), 1064-1084. https://doi.org/10.1137/120893549
• Dalmau, V., & Krokhin, A. (2013). Robust Satisfiability for CSPs: Hardness and Algorithmic Results. ACM Transactions on Computation Theory, 5(4), Article 15. https://doi.org/10.1145/2540090
• Krokhin, A., & Marx, D. (2012). On the hardness of losing weight. ACM Transactions on Algorithms, 8(2), Article 19. https://doi.org/10.1145/2151171.2151182
• Carvalho, C., Dalmau, V., & Krokhin, A. (2011). Two new homomorphism dualities and lattice operations. Journal of Logic and Computation, 21(6), 1065-1092. https://doi.org/10.1093/logcom/exq030
• Carvalho, C., Dalmau, V., & Krokhin, A. (2010). CSP duality and trees of bounded pathwidth. Theoretical Computer Science, 411(34-36), 3188-3208. https://doi.org/10.1016/j.tcs.2010.05.016
• Feder, T., Hell, P., Jonsson, P., Krokhin, A., & Nordh, G. (2010). Retractions to pseudoforests. SIAM Journal on Discrete Mathematics, 24(1), 101-112. https://doi.org/10.1137/080738866
• Krokhin, A., & Marx, D. (2010). On the hardness of losing weight. https://doi.org/10.1007/978-3-540-70575-8_54
• Jonsson, P., Krokhin, A., & Kuivinen, F. (2009). Hard constraint satisfaction problems have hard gaps at location 1. Theoretical Computer Science, 410(38-40), 3856-3874. https://doi.org/10.1016/j.tcs.2009.05.022
• Boerner, F., Bulatov, A., Chen, H., Jeavons, P., & Krokhin, A. (2009). The complexity of constraint satisfaction games and QCSP. Information and Computation, 207(9), 923-944. https://doi.org/10.1016/j.ic.2009.05.003
• Deineko, V., Jonsson, P., Klasson, M., & Krokhin, A. (2008). The approximability of MAX CSP with fixed-value constraints. Journal of the ACM, 55(4), Article 16. https://doi.org/10.1145/1391289.1391290
• Jonsson, P., & Krokhin, A. (2008). Computational complexity of auditing finite attributes in statistical databases. Journal of Computer and System Sciences, 74(5), 898-909. https://doi.org/10.1016/j.jcss.2008.02.002
• Dalmau, V., Krokhin, A., & Larose, B. (2008). Retractions onto series-parallel posets. Discrete Mathematics, 308(11), 2104-2114. https://doi.org/10.1016/j.disc.2006.08.010
• Dalmau, V., & Krokhin, A. (2008). Majority constraints have bounded pathwidth duality. European Journal of Combinatorics, 29(4), 821-837. https://doi.org/10.1016/j.ejc.2007.11.020
• Krokhin, A., & Larose, B. (2008). Maximizing supermodular functions on product lattices, with application to maximum constraint satisfaction. SIAM Journal on Discrete Mathematics, 22(1), 312-328. https://doi.org/10.1137/060669565
• Creignou, N., Hermann, M., Krokhin, A., & Salzer, G. (2008). Complexity of clausal constraints over chains. Theory of Computing Systems, 42(2), 239-255. https://doi.org/10.1007/s00224-007-9003-z
• Jonsson, P., & Krokhin, A. (2007). Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights. Journal of Computer and System Sciences, 73(5), 691-702. https://doi.org/10.1016/j.jcss.2007.02.001
• Dalmau, V., Krokhin, A., & Larose, B. (2007). First-order definable retraction problems for posets and reflexive graphs. Journal of Logic and Computation, 17(1), 31-51. https://doi.org/10.1093/logcom/exl014
• Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2006). The complexity of soft constraint satisfaction. Artificial Intelligence, 170(11), 983-1016. https://doi.org/10.1016/j.artint.2006.04.002
• Jonsson, P., Klasson, M., & Krokhin, A. (2006). The approximability of three-valued Max CSP. SIAM Journal on Computing, 35, 1329-1349
• Krokhin, A., & Rosenberg, I. (2006). A monoidal interval of clones of selfdual functions. Journal of automata, languages and combinatorics, 11(2),
• Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2005). Supermodular functions and the complexity of MAX CSP. Discrete Applied Mathematics, 149(1-3), 53-72. https://doi.org/10.1016/j.dam.2005.03.003
• Bulatov, A., Jeavons, P., & Krokhin, A. (2005). Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34(3), 720-742. https://doi.org/10.1137/s0097539700376676
• Jonsson, P., & Krokhin, A. (2004). Recognizing frozen variables in constraint satisfaction problems. Theoretical Computer Science, 329(1-3), 93-113. https://doi.org/10.1016/j.tcs.2004.08.006
• Jonsson, P., & Krokhin, A. (2004). Complexity classification in qualitative temporal constraint reasoning. Artificial Intelligence, 160(1-2), 35-51. https://doi.org/10.1016/j.artint.2004.05.010
• Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2004). A maximal tractable class of soft constraints. Journal of Artificial Intelligence Research, 22, 1-22. https://doi.org/10.1613/jair.1400
• Krokhin, A., Jeavons, P., & Jonsson, P. (2004). Constraint satisfaction problems on intervals and lengths. SIAM Journal on Discrete Mathematics, 17(3), 453-477. https://doi.org/10.1137/s0895480102410201
• Krokhin, A., Jeavons, P., & Jonsson, P. (2003). Reasoning about temporal relations : the maximal tractable subalgebras of Allen's interval algebra. Journal of the ACM, 50(5), 591-640. https://doi.org/10.1145/876638.876639
• Krokhin, A., & Larose, B. (2002). A monoidal interval of isotone clones on a finite chain. Acta scientiarum mathematicarum, 68(1-2), 37-62
• Krokhin, A. (2001). On clones, transformation monoids and finite Boolean algebras. Algebra Universalis, 46(1-2), 231-236
• Krokhin, A., & Schweigert, D. (2001). On clones preserving a reflexive binary relation. Acta scientiarum mathematicarum, 67(3-4), 461-473
• Krokhin, A. (2001). Congruences of clone lattices, II. Order, 18(2), 151-159