Professor Andrei Krokhin, MSc, PhD
(email at firstname.lastname@example.org)
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.
School of Engineering and Computing Sciences
- Algorithms and Complexity Research Group
Department of Computer Science
- Algorithms and Complexity
- Combinatorics of graphs and ordered sets
- Computational complexity
- Homomorphism problems
- Mathematics of constraint satisfaction
- Universal algebra and logic in computer science
- 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.
- 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