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

• 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
• 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
• 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. (2019, November). The complexity of 3-colouring H-colourable graphs. Presented at Foundations of Computer Science (FOCS), Baltimore, USA
• Bulin, J., Krokhin, A., & Oprsal, J. (2019, June). Algebraic approach to promise constraint satisfaction. Presented at ACM Symposium on Theory of Computing (STOC), Phoenix, USA
• Dalmau, V., Kozik, M., Krokhin, A., Makarychev, K., Makarychev, Y., & Oprsal, J. (2017, January). Robust algorithms with polynomial loss for near-unanimity CSPs. Presented at Symposium on Discrete Algorithms, Barcelona
• Kolmogorov, V., Krokhin, A., & Rolinek, M. (2015, December). The Complexity of General-Valued CSPs. Presented at 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), Berkeley
• Egri, L., Krokhin, A., Larose, B., & Tesson, P. (2010, December). The complexity of the list homomorphism problem for graphs. Presented at Symposium on Theoretical Aspects of Computer Science., Nancy, France
• Carvalho, C., Dalmau, V., & Krokhin, A. (2008, June). Caterpillar duality for constraint satisfaction problems. Presented at 23rd Annual IEEE Symposium on Logic in Computer Science (LICS) 2008, Pittsburgh, Pennsylvania
• Deineko, V., Jonsson, P., Klasson, M., & Krokhin, A. (2005, December). Supermodularity on chains and complexity of maximum constraint satisfaction. Presented at 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb'05)
• Krokhin, A., & Larose, B. (2005, December). Maximum constraint satisfaction on diamonds. Presented at 11th International Conference on Principles and Practice of Constraint Programming {(CP'05)
• Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2004, December). Identifying efficiently solvable cases of Max CSP. Presented at 21st International Symposium on Theoretical Aspects of Computer Science
• Dalmau, V., Krokhin, A., & Larose, B. (2023, July). First-Order Definable Retraction Problems for Posets and Reflexive Graphs. Presented at 19th Annual IEEE Symposium on Logic in Computer Science (LICS'04), Turku, Finland
• Krokhin, A., Bulatov, A., & Jeavons, P. (2003, May). Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey. Presented at 33rd International Symposium on Multiple-Valued Logic (ISMVL'03)
• Krokhin, A., & Larose, B. (2003, January). Solving order constraints in logarithmic space. Presented at Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science {(STACS'03) Berlin, Berlin
• Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2003, December). Soft constraints: complexity and multimorphisms. Presented at Proceedings of 9th International Conference on Principle and Practice of Constraint Programming {(CP'03)
• Boerner, F., Bulatov, A., Jeavons, P., & Krokhin, A. (2003, December). Quantified constraints: Algorithms and complexity. Presented at 17th International Workshop on Computer Science Logic
• Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2003, December). A tractable class of soft constraints. Presented at 18th International Joint Conference on Artificial Intelligence {(IJCAI'03)
• Krokhin, A., & Jonsson, P. (2002, December). Extending the Point Algebra into the Qualitative Algebra. Presented at Proceedings of 9th International Workshop on Temporal Representation and Reasoning ({TIME'02})
• Krokhin, A., Jeavons, P., & Jonsson, P. (2002, December). The complexity of constraints on intervals and lengths. Presented at Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science {(STACS'02)
• Krokhin, A., Jeavons, P., & Jonsson, P. (2001, December). A complete classification of complexity in Allen's algebrain the presence of a non-trivial basic relation. Presented at 17th International Joint Conference on Artificial Intelligence, {(IJCAI'01)
• Bulatov, A., Krokhin, A., Safin, K., Semigrodskikh, A., & Sukhanov, E. (2001, December). On the structure of clone lattices, II
• Bulatov, A., Krokhin, A., & Jeavons, P. (2001, December). The complexity of maximal constraint languages. Presented at 33rd ACM Symposium on the Theory of Computing(STOC), Crete, Greece

Journal Article

• Ciardo, L., Kozik, M., Krokhin, A., Nakajima, T.-V., & Živný, S. (online). 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise. ACM Transactions on Computational Logic, https://doi.org/10.1145/3719007
• Krokhin, A., & Marx, D. (online). On the hardness of losing weight. https://doi.org/10.1007/978-3-540-70575-8_54
• Dalmau, V., Krokhin, A., & Opršal, J. (2024). Functors on Relational Structures Which Admit Both Left and Right Adjoints. SIAM Journal on Discrete Mathematics, 38(3), 2041-2068. https://doi.org/10.1137/23m1555223
• 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
• 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
• Krokhin, A., & Rosenberg, I. (2006). A monoidal interval of clones of selfdual functions. Journal of automata, languages and combinatorics, 11(2),
• Jonsson, P., Klasson, M., & Krokhin, A. (2006). The approximability of three-valued Max CSP. SIAM Journal on Computing, 35, 1329-1349
• 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