Staff in Computer Science

Dr Andrei Krokhin, MSc, PhD Ural State
(email at andrei.krokhin@durham.ac.uk)
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.
