Grant: Discovery Grants Program - Individual

The constraint satisfaction problem (CSP) provides a general framework in which it is possible to express, in a natural way, a wide variety of problems including many crucial real-world problems in scheduling, routing, databases, etc. The aim in a CSP is to find an assignment of values to a given set of variables, subject to constraints on the values which can be simultaneously assigned to certain specified subsets of variables. In the counting constraint satisfaction problem the objective is to find the number of such assignments. The CSP is therefore very important in a number of applications, both theoretical and practical. In theoretical applications we look for new algorithmic ideas that can help to solve problems that could not be solved before, to improve the existing algorithms, to design more general and uniform algorithms, and to find evidence that certain problems are not efficiently solvable in the general case. In practical applications, constraint and satisfiability solvers are now standard tools in a wide range of areas from scheduling to hardware verification. Advances in the study of the CSP will speed up such solvers and expand their area of applicability. This project focuses on the theoretical side of the CSP research. One of its main goals is to precisely understand which CSPs and counting CSPs can be solved efficiently and design efficient solution algorithms. Major progress has been made very recently in understanding the hardness of the CSP, and a natural next step is to extend the methods used to achieve this breakthrough to a wider range of problems. One of the most efficient tools in the study of the CSP applies methods of abstract algebra. We plan to develop these methods to work in other areas. One of such areas is approximate counting. This area has surprising connections to statistical physics, where such numbers affect the properties of large ensembles of particles, and, in particular, help to locate phase transition thresholds, at which, for instance, liquid turns to gas. While the CSP and the counting CSP are well established research areas, we also plan to venture into very new territory. A further generalization of the CSP, the Promise CSP, has been recently proposed, in which, given two CSP instances, a more restrictive one, and a more relaxed one, we are promised that the restrictive instance has a solution and asked to find a solution of the relaxed instance. This problem has much greater expressive power than the regular CSP. Certain elements of the algebraic approach to the Promise CSP have been developed recently, and a project aiming at a classification of Promise CSPs is very active.