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.

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

• ACiD: Algorithms and Complexity

• 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

• Krokhin, A. & Živný, S. (2017). The complexity of Valued CSPs. In The Constraint Satisfaction Problem: Complexity and Approximability. Krokhin, A. & Živný, S. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 7: 233-266.
• Barto, L., Krokhin, A. & Willard, R. (2017). Polymorphisms, and how to use them. In The Constraint Satisfaction Problem: Complexity and Approximability. Krokhin, A. & Živný, S. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 7: 1-44.
• Dalmau, V., Krokhin, A. & Manokaran, R. (2015). Towards a Characterization of Constant-Factor Approximable Min CSPs. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms: San Diego, California, USA, January 4-6, 2015. Indyk, Piotr New York: Society for Industrial and Applied Mathematics (SIAM). 847-857.
• Bulatov, A., Krokhin, A. & Larose, B. (2008). Dualities for constraint satisfaction problems. In Complexity of Constraints. Creignou, N. Kolaitis, Ph.G. & Vollmer, H. Springer. 93-124.
• Krokhin, A., Bulatov, A. & Jeavons, P. (2005). The complexity of constraint satisfaction: an algebraic approach. In Structural Theory of Automata, Semigroups, and Universal Algebra. Kudryavtsev, Valery B. & Rosenberg, Ivo G. Dordrecht, The Netherlands: Springer Netherlands. 207: 181-213.

Conference Paper

• Krokhin, A. & Oprsal, J. (2020), The complexity of 3-colouring H-colourable graphs, in Zuckerman, D. eds, Foundations of Computer Science (FOCS). Baltimore, USA, IEEE, Piscataway, NJ, 1227-1239.
• Bulin, J., Krokhin, A. & Oprsal, J. (2019), Algebraic approach to promise constraint satisfaction, ACM Symposium on Theory of Computing (STOC). Phoenix, USA, ACM, New York, 602-613.
• Dalmau, V., Kozik, M., Krokhin, A., Makarychev, K., Makarychev, Y. & Oprsal, J. (2017), Robust algorithms with polynomial loss for near-unanimity CSPs, in Klein, Philip N. eds, ACM-SIAM Symposium on Discrete Algorithms. Barcelona, SIAM, 340-357.
• Kolmogorov, V., Krokhin, A. & Rolinek, M. (2015), The Complexity of General-Valued CSPs, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). Berkeley, CA, IEEE, Piscataway, NJ, 1246-1258.
• Egri, L., Krokhin, A., Larose, B. & Tesson, P. (2010), The complexity of the list homomorphism problem for graphs, in Marion, J.-Y. & Schwentick, T. eds, LIPIcs 5: Symposium on Theoretical Aspects of Computer Science. Nancy, France, Nancy, 335-346.
• Carvalho, C., Dalmau, V. & Krokhin, A. (2008), Caterpillar duality for constraint satisfaction problems, LICS '08 Proceedings of the 2008 23rd Annual IEEE Symposium on Logic in Computer Science 23rd Annual IEEE Symposium on Logic in Computer Science (LICS) 2008. Pittsburgh, Pennsylvania IEEE Computer Society, Los Alamitos, CA, 307-316
• Deineko, V., Jonsson, P., Klasson, M. & Krokhin, A. (2005), Supermodularity on chains and complexity of maximum constraint satisfaction, in S.~Felsner eds, DMTCS Proceedings AE: 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb'05). Discrete Mathematics and Theoretical Computer Science, 51-56.
• Dalmau, V., Krokhin, A. & Larose, B. (2004), First-Order Definable Retraction Problems for Posets and Reflexive Graphs, Proceedings of 19th International Symposium on Logic in Computer Science {(LICS'04) 19th Annual IEEE Symposium on Logic in Computer Science (LICS'04). Turku, Finland IEEE Computer Society, Turku, 232-241.
• Cohen, D., Cooper, M., Jeavons, P. & Krokhin, A. (2004), Identifying efficiently solvable cases of Max CSP, in M.~Habib and V.~Diekert eds, Lecture Notes in Computer Science 2996: 21st International Symposium on Theoretical Aspects of Computer Science. Springer Verlag, 152-163.
• Cohen, D., Cooper, M., Jeavons, P. & Krokhin, A. (2003), A tractable class of soft constraints, in G.~Gottlob and T.~Walsh eds, 18th International Joint Conference on Artificial Intelligence {(IJCAI'03). Morgan Kaufmann, 209-214.
• Boerner, F., Bulatov, A., Jeavons, P. & Krokhin, A. (2003), Quantified constraints: Algorithms and complexity, in M.~Baaz and J.A.~Makowsky eds, Lecture Notes in Computer Science 2803: 17th International Workshop on Computer Science Logic. Springer Verlag, 58-70.
• Krokhin, A., Bulatov, A. & Jeavons, P. (2003), Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey, 33rd International Symposium on Multiple-Valued Logic ({ISMVL'03}). IEEE Computer Society, 343-351.
• Krokhin, A. & Larose, B. (2003), Solving order constraints in logarithmic space, in H.~Alt and M.~Habib eds, Lecture Notes in Computer Science 2607: Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science {(STACS'03). Berlin, Springer-Verlag, Berlin, 379-390.
• Cohen, D., Cooper, M., Jeavons, P. & Krokhin, A. (2003), Soft constraints: complexity and multimorphisms, in F.~Rossi eds, Lecture Notes in Computer Science 2833: Proceedings of 9th International Conference on Principle and Practice of Constraint Programming {(CP'03). Springer Verlag, 244-258.
• Krokhin, A. & Jonsson, P. (2002), Extending the Point Algebra into the Qualitative Algebra, in M.~Fisher eds, Proceedings of 9th International Workshop on Temporal Representation and Reasoning ({TIME'02}). IEEE Computer Society, 28-35.
• Krokhin, A., Jeavons, P. & Jonsson, P. (2002), The complexity of constraints on intervals and lengths, in H.~Alt and A.~Ferreira eds, Lecture Notes in Computer Science 2285: Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science {(STACS'02). Springer Verlag, 443-454.
• Bulatov, A., Krokhin, A., Safin, K., Semigrodskikh, A. & Sukhanov, E. (2001), On the structure of clone lattices, II, 7: 379-389.
• Bulatov, A., Krokhin, A. & Jeavons, P. (2001), The complexity of maximal constraint languages, 33rd ACM Symposium on the Theory of Computing(STOC). Crete, Greece, ACM Press, Crete, 667-674.
• 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 eds, 17th International Joint Conference on Artificial Intelligence, {(IJCAI'01). Morgan Kaufmann, 83-88.

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

• Krokhin, Andrei, Opršal, Jakub, Wrochna, Marcin & Živný, Stanislav (2023). Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing 52(1): 38-79.
• Barto, Libor, Bulín, Jakub, Krokhin, Andrei & Opršal, Jakub (2021). Algebraic Approach to Promise Constraint Satisfaction. Journal of the ACM 68(4): 28, 1-66.
• 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.
• 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.
• 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.
• Kolmogorov, V., Krokhin, A. & Rolínek, M. (2017). The complexity of general-valued CSPs. SIAM Journal on Computing 46(3): 1087-1110.
• Carvalho, C. & Krokhin, A. (2016). On algebras with many symmetric operations. International Journal of Algebra and Computation 26(05): 1019-1032.
• Kozik, M., Krokhin, A., Valeriote, M. & Willard, R. (2015). Characterizations of several Maltsev conditions. Algebra Universalis 73(3): 205-224.
• Huber, A. & Krokhin, A. (2014). Oracle Tractability of Skew Bisubmodular Functions. SIAM Journal on Discrete Mathematics 28(4): 1828-1837.
• Huber, A., Krokhin, A. & Powell, R. (2014). Skew Bisubmodularity and Valued CSPs. SIAM Journal on Computing 43(3): 1064-1084.
• Jeavons, P., Krokhin, A. & Živný, S. (2014). The Complexity of Valued Constraint Satisfaction. Bulletin of the EATCS 113: 21-55.
• Dalmau, V. & Krokhin, A. (2013). Robust Satisfiability for CSPs: Hardness and Algorithmic Results. ACM Transactions on Computation Theory 5(4): 15.
• Krokhin, A. & Marx, D. (2012). On the hardness of losing weight. ACM Transactions on Algorithms (TALG) 8(2): 19.
• Carvalho, C., Dalmau, V. & Krokhin, A. (2011). Two new homomorphism dualities and lattice operations. Journal of Logic and Computation 21(6): 1065-1092.
• Krokhin, A. & Marx, D. (2010). On the hardness of losing weight. ACM Transactions on Algorithms
• Feder, T., Hell, P., Jonsson, P., Krokhin, A. & Nordh, G. (2010). Retractions to pseudoforests. SIAM Journal on Discrete Mathematics 24(1): 101-112.
• Carvalho, C., Dalmau, V. & Krokhin, A. (2010). CSP duality and trees of bounded pathwidth. Theoretical Computer Science 411(34-36): 3188-3208.
• 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.
• 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.
• Dalmau, V. & Krokhin, A. (2008). Majority constraints have bounded pathwidth duality. European Journal of Combinatorics 29(4): 821-837.
• Dalmau, V., Krokhin, A. & Larose, B. (2008). Retractions onto series-parallel posets. Discrete Mathematics 308(11): 2104-2114.
• 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.
• Deineko, V., Jonsson, P., Klasson, M. & Krokhin, A. (2008). The approximability of MAX CSP with fixed-value constraints. Journal of the ACM 55(4): 16.
• Creignou, N., Hermann, M., Krokhin, A. & Salzer, G. (2008). Complexity of clausal constraints over chains. Theory of Computing Systems 42(2): 239-255.
• Jonsson, P. & Krokhin, A. (2008). Computational complexity of auditing finite attributes in statistical databases. Journal of Computer and System Sciences 74(5): 898-909.
• 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.
• 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.
• 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.G. (2006). A monoidal interval of clones of selfdual functions. Journal of Automata, Languages and Combinatorics 11(2): 189–208.
• Cohen, D., Cooper, M., Jeavons, P. & Krokhin, A. (2006). The complexity of soft constraint satisfaction. Artificial intelligence 170(11): 983-1016.
• 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.
• Bulatov, A., Jeavons, P. & Krokhin, A. (2005). Classifying the complexity of constraints using finite algebras. SIAM journal on computing 34(3): 720-742.
• Cohen, D., Cooper, M., Jeavons, P. & Krokhin, A. (2004). A maximal tractable class of soft constraints. Journal of Artificial Intelligence Research 22: 1-22.
• Jonsson, P. & Krokhin, A. (2004). Complexity classification in qualitative temporal constraint reasoning. Artificial Intelligence 160(1-2): 35-51.
• Krokhin, A., Jeavons, P. & Jonsson, P. (2004). Constraint satisfaction problems on intervals and lengths. SIAM Journal on Discrete Mathematics 17(3): 453-477.
• Jonsson, P. & Krokhin, A. (2004). Recognizing frozen variables in constraint satisfaction problems. Theoretical Computer Science 329(1-3): 93-113.
• 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.
• 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). Congruences of clone lattices, II. Order 18(2): 151-159.
• Krokhin, A. & Schweigert, D. (2001). On clones preserving a reflexive binary relation. Acta Sci. Math. (Szeged) 67(3-4): 461-473.
• Krokhin, A. (2001). On clones, transformation monoids and finite Boolean algebras. Algebra Universalis 46(1-2): 231-236.