International Workshop on Mathematics of Constraint Satisfaction: Algebra, Logic, and Graph Theory
Lead Research Organisation:
Durham University
Department Name: Computer Science
Abstract
The constraint satisfaction problem, or CSP for short, provides ageneral framework in which it is possible to express, in a naturalway, a wide variety of computational problems, including satisfiability and graph colourability. The aim in a constraint satisfaction problem is to find an assignment of values to a given set of variables, subject to constraints on the values which can be assigned simultaneously to certain specified subsets of variables.The study of constraint satisfaction problems is a very active area of research. It has originated in aritificial intelligence, and is now spread over various areas of computer science and mathematics. We seek funds to support an international workshop on mathematics of constraintsatisfaction which is intended to bring together specialists from many different areas of mathematics and computer science with an interest in this exciting interdisciplinary area.
Organisations
| Description | This workshop brought together, for the first time, all the leading specialists on various mathematical approaches to constraint satisfaction, as well as many researchers from many different areas of mathematics and computer science with an interest in this exciting interdisciplinary area. The programme included three substantial tutorials outlining the basics of the algebraic, logical, and combinatorial approaches to the CSP, given by P.Jeavons, Ph.Kolaitis, and P.Hell, respectively. These tutorials were designed to ensure that all participants were equipped with the necessary preliminary knowledge of all of the fundamental mathematical approaches. The main part of the programme consisted of 11 one-hour plenary lectures given by world-leading specialists in the above four topics. This ensured that all participants gained a complete state-of-the-art picture of the research area. The plenary lectures were given by A.Bulatov, H.Chen, and P.Jonsson (algebra), A.Atserias and I.Stewart (logic), G.Gottlob and J.Nesetril (combinatorics), V.Dalmau and B.Larose (combinations of the three approaches), N.Creignou (Boolean CSP) and J.Hastad (inapproximability of CSP). In addition to these plenary talks, there were 11 invited 30-minute talks which covered a broad range of other topics, including the use of mathematics in more applied CSP research. The workshop can be called a ``community-creating event'' because many leading researchers in different aspects of the area met there for the first time, and discussed and compared the different approaches to a significant extent. Now researchers from different research areas are much more aware of the deep mathematical insights and challenges present in the mathematical theory of constraint satisfaction. This workshop started a series of international meetings (at least one every year) that bring together specialists in different aspects of CSP. |
| Exploitation Route | The main finding of this event was that there are many ways in which researchers in different aspects of CSP can collaborate. A lot of collaborative activity happened that can be traced back to this workshop. |
| Sectors | Digital/Communication/Information Technologies (including Software) |
| URL | http://www.comlab.ox.ac.uk/mathscsp/ |