Professor Andrei Krokhin's Outputs (2)

Hard constraint satisfaction problems have hard gaps at location 1 (2009)
Journal Article
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. https://doi.org/10.1016/j.tcs.2009.05.022

An instance of the maximum constraint satisfaction problem (Max CSP) is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constraints. Max CSP captures m... Read More about Hard constraint satisfaction problems have hard gaps at location 1.

The complexity of constraint satisfaction games and QCSP (2009)
Journal Article
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. https://doi.org/10.1016/j.ic.2009.05.003

We study the complexity of two-person constraint satisfaction games. An instance of such a game is given by a collection of constraints on overlapping sets of variables, and the two players alternately make moves assigning values from a finite domain... Read More about The complexity of constraint satisfaction games and QCSP.