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)
- Krokhin, A., Bulatov, A. & Jeavons, P. 2005. The complexity of constraint satisfaction: an algebraic approach. In Springer Verlag. 207: 181-213.
- 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.