BA in Mathematics (University of Oxford, 1983); PGCE (University of Nottingham, 1984); MSc in Medical Statistics (University of Leicester, 1986), PhD in Computer Science (Royal Holloway, University of London, 1991); Lecturer and Reader in Computer Science (Royal Holloway, University of London, 1988-99); joined Oxford and St Anne’s in 1999.
Undergraduate: All core computer science courses.
Graduate: Constraint satisfaction problems, complexity.
Computational complexity, and mathematical analysis of computational problems, especially of constraint satisfaction problems. Algorithms for combinatorial problems. Applications to bioinformatics.
David Cohen, Martin Cooper, Peter Jeavons and Andrei Krokhin, ‘The complexity of soft constraint satisfaction’, in Artificial Intelligence 170 (2006), 983-1016
David Cohen and Peter Jeavons, ‘The complexity of constraint languages’, in Handbook of Constraint Programming, 2006, Chapter 8
David Cohen, Peter Jeavons, Christopher Jefferson, Karen Petrie and Barbara Smith, ‘Symmetry definitions for constraint satisfaction problems’, in Constraints 11, 2006, 115-37
Andrei Bulatov, Peter Jeavons and Andrei Krokhin, ‘Classifying the complexity of constraints using finite algebras’, in SIAM Journal on Computing 34, 2005, 720-42