skip to content

Mathematics of Constraint Satisfaction: Logic, Algebra and Graph Theory

20th March 2006 to 24th March 2006

Organisers: Peter Jeavons (Oxford) and Andrei Krokhin (Durham)

Workshop Theme

The study of constraint satisfaction problems (CSPs) began in the 1970's in artificial intelligence, where this paradigm is now as popular as ever, with hundreds of researchers using this framework to model and solve a wide variety of problems. In 1978, Thomas Schaefer published a seminal paper on the complexity classification of Boolean CSPs, and since then the importance of the CSP in theoretical computer science has continued to grow. For example, many standard complete problems for standard complexity classes are variants of CSPs, and some of the first optimal inapproximability results in combinatorial optimization were proved for certain CSPs.

During the last 10 years, researchers studying the complexity of CSPs have discovered deep connections between this framework and many areas of mathematics, the strongest links currently being with universal algebra and lattice theory, logic and finite model theory, and graph theory and combinatorics. The corner-stone of logical and combinatorial approaches to CSP is the fact that many questions about constraint satisfaction can be stated as questions about homomorphisms between relational structures (e.g., graphs). The universal-algebraic approach assigns a finite algebra to every CSP and employs the properties of the algebra to study the properties of the CSP.

The workshop will consist of three 1.5-hour tutorials (one on each topic of the workshop) outlining the basics of the three mathematical approaches to CSP, 11 1-hour research expositions providing state-of-the-art information on mathematical developments related to constraint satisfaction, and a number of 30-minute talks on current research.

The purpose of the workshop is to:

  • enhance the synergy between different mathematical aspects of CSP research
  • form new connections between theoretical researchers and more applied researchers working on constraint satisfaction
  • provide the participants with the state-of-the-art information on the subject of the workshop
  • provide a forum for a comprehensive discussion of mathematical techniques which can be used to analyze the structure of a wide variety of computational problems
  • explore and disseminate new links between Computer Science and Mathematics
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons