Staff in Computer Science

Dr Andrei Krokhin, MSc, PhD Ural State

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.

Research Groups

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. (Additional information) (View publication online)
2: Bulatov, A., Jeavons, P. & Krokhin, A. 2005. Classifying the complexity of constraints using finite algebras. SIAM journal on computing 34(3): 720-742. (Additional information) (View publication online)
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. (Additional information) (View publication online)
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. (Additional information) (View publication online)
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. (Additional information) (View publication online)
Krokhin, A., Bulatov, A. & Jeavons, P. 2005. The complexity of constraint satisfaction: an algebraic approach. In Springer Verlag. 207: 181-213.
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. (Additional information) (View publication online)
Krokhin, A. & Marx, D. (2008). On the hardness of losing weight. Automata, Languages and Programming, 35th International Colloquium (ICALP 2008), Reykjavik, Iceland, Springer. (Additional information) (View publication online)
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. (Additional information) (View publication online)
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. (Additional information) (View publication online)
Creignou, N., Hermann, M., Krokhin, A. & Salzer, G. 2008. Complexity of clausal constraints over chains. Theory of Computing Systems 42(2): 239-255. (Additional information) (View publication online)
Jonsson, P. & Krokhin, A. 2008. Computational complexity of auditing finite attributes in statistical databases. Journal of Computer and System Sciences 74(5): 898-909. (Additional information) (View publication online)
Dalmau, V. & Krokhin, A. 2008. Majority constraints have bounded pathwidth duality. European Journal of Combinatorics 29(4): 821-837. (Additional information) (View publication online)
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. (Additional information) (View publication online)
Dalmau, V., Krokhin, A. & Larose, B. 2008. Retractions onto series-parallel posets. Discrete Mathematics 308(11): 2104-2114. (Additional information) (View publication online)
Deineko, V., Jonsson, P., Klasson, M. & Krokhin, A. 2008. The approximability of MAX CSP with fixed-value constraints. Journal of the ACM 55(4): 37. (Additional information) (View publication online)
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. (Additional information)
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. (Additional information)
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 varaibles in constraint satisfaction problems. Theoretical Computer Science 329(1-3): 93-113.

Show all publications