Profile

Professor Andrei Krokhin, MSc, PhD

Chair of Computer Science in the School of Engineering and Computing Sciences

Telephone: +44 (0) 191 33 41743

Room number: CS3.05 (Christopherson)

Biography

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 Reader in Computer Science in Durham since September 2004.

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.

Research Groups

School of Engineering and Computing Sciences

Algorithms and Complexity Research Group

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.
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.
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, 335-346.
Carvalho, C., Dalmau, V. & Krokhin, A. (2008). Caterpillar duality for constraint satisfaction problems. 23rd Annual IEEE Symposium on Logic in Computer Science (LICS 2008), Pittsburgh, USA, IEEE Computer Society.
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.

Show all publications

Grants Awarded

2006: International Workshop on Mathematics of Constraint Satisfaction: Algebra, Logic, and Graph Theory
2005: Combining Approaches in Classifying Complexity of Constraints
2005: Constraint Satisfaction Problems: Complexity and Approximability (EPSRC Advanced Research Fellowship)
2004: Complexity of Constraint Optimisation on ordered Domains: An initial Study
2001: Algebraic Structural Methods and Complexity of Constraint Satisfaction