Workshop
Home
Tutorials
Plenary Lectures
Short Talks
Programme
Participants
Photos
Contacts

Organizers
Andrei Krokhin
Peter Jeavons

Travel
Venue
Travel and Maps
Accommodation

The immensely positive feedback from participants leads us to believe that the workshop was a huge success! Thanks are due to the hard work of all the speakers, the staff at Oxford and the sponsors [not to mention the organizers! - Martin].

The open problems [ pdf ] raised at the workshop have now been compiled by the organizers and are available for download. If you have any comments or suggestions for these or other open problems please let us know via the email links on the contacts page.

The slides used by all speakers are available on the programme page and also on the individual tutorials, plenary lectures and short talks pages. By request, we have made PDF the unifying format for these slides. Where speakers have provided only PowerPoint or PostScript files we have converted these to PDF. (Conversions are not always accurate, particularly with animations, in which case please try the non-PDF version of the slides where possible.)

Enhanced photos of all the speakers have been generated and organized into appropriate galleries. We also have photos of the banquet, the excursion to Oxford (some very nice photos here) and even the attendees. Please take a look!

The International Workshop on Mathematics of Constraint Satisfaction: Algebra, Logic and Graph Theory is a satellite workshop associated with the programme on Logic and Algorithms hosted by the Isaac Newton Institute in Cambridge during the first six months of 2006.

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 3 1½-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 ½-hour talks on current research.

Most constraint researchers are computer scientists, and there are few existing mechanisms to encourage interaction between these researchers and mathematicians. The Logic and Algorithms programme at the Isaac Newton Institute in the first half of 2006 provides an unusually good opportunity to publicize the constraint satisfaction problem and its challenges to the wider mathematical community, and to attract more mathematicians to the study of this problem.

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

The workshop is supported by the UK EPSRC, the Isaac Newton Institute in Cambridge, the Symmetry and Search Network (SymNet), the Association for Constraint Programming (ACP), Microsoft Research, IBM, Intel and ILOG.