Professor Andrei Krokhin, MSc, PhD

Personal web page

(email at andrei.krokhin@durham.ac.uk)

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 Groups

Department of Computer Science

• Algorithms and Complexity

Research Interests

• Combinatorics of graphs and ordered sets
• Computational complexity
• Homomorphism problems
• Mathematics of constraint satisfaction
• Universal algebra and logic in computer science

Selected Publications

• 1: Cohen, D., Cooper, M., Jeavons, P. & Krokhin, A. (2006). The complexity of soft constraint satisfaction. Artificial intelligence 170(11): 983-1016.
• 2: Bulatov, A., Jeavons, P. & Krokhin, A. (2005). Classifying the complexity of constraints using finite algebras. SIAM journal on computing 34(3): 720-742.
• 3: 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.
• 4: 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. & Zivny, S. (2017). The Constraint Satisfaction Problem: Complexity and Approximability. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
• 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.
• 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.
• 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.
• 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.
• Carvalho, C., Dalmau, V. & Krokhin, A. (2010). CSP duality and trees of bounded pathwidth. Theoretical Computer Science 411(34-36): 3188-3208.
• 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.
• 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.
• 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. (2008). Majority constraints have bounded pathwidth duality. European Journal of Combinatorics 29(4): 821-837.
• 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.
• Dalmau, V., Krokhin, A. & Larose, B. (2008). Retractions onto series-parallel posets. Discrete Mathematics 308(11): 2104-2114.
• 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.
• 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., 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. & 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

Show all publications

Supervises

• Dr Catarina Carvalho

Indicators of Esteem

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

Selected Grants