June 17, 2024

Summer Thematic Program on the Mathematics of Constraint Satisfaction
at the Fields Institute, Toronto

Venkatesan Guruswami, Carnegie Mellon University
Pavol Hell, Simon Fraser University
Matt Valeriote, McMaster University
Ross Willard, University of Waterloo


During July and August 2011, the Fields Institute will host a thematic program on the Mathematics of Constraint Satisfaction. The program will include a 5-day summer school, three focused workshops, the Coxeter Lectures, regular weekly seminars, and extended periods of time for in-residence researchers and students for intensive study. The program will bring together researchers from various communities within pure mathematics and theoretical computer science.

Outline of Scientific Activities

The main activities of the program will be concentrated around a series of three workshops, a summer school, and the Coxeter Lectures. The summer school will take place during the last week of June, 2011 and the three workshops will be held at regular intervals throughout the summer. The Coxeter Lectures will be given by Moshe Vardi (Rice) on July 11-13, 2011.

Participation in the Program

All scientific events are open to the mathematical sciences community, but visitors are requested to indicate their interest in participating in some or all of the planned events by filling out the information form found on the program website. The information form can also be used to request office space or funding. Fields scientific programs are devoted to research in the mathematical sciences, and enhanced graduate and post-doctoral training opportunities. Part of the mandate of the Institute is to broaden and enlarge the community, and to encourage the participation of women and members of visible minority groups in our scientific programs.


Requests for support or office space may be submitted at any time by filling out the application form found on the program website. The organizing committee will start to review requests in late February of 2011.

Additional Information

For additional information on the program, please send an email to thematic(at) . To receive updates on the program please subscribe to our mailing list at .

Details of Scientific Activities

Program Visitors Seminars

June 26-30, 2011
Fields Summer School

Each day of the summer school will consist of four 90 minute lectures plus time set aside for school participants and instructors to meet to discuss questions and problems related to the lectures. Lecture notes and problem sets will be prepared in advance and posted on the program website. A primary goal of the summer school is to provide the participants with a thorough and intense introduction to the main themes of the summer program.

The four threads of the summer school, along with the lecturers are:

* An Introduction to the CSP: Andrei Krokhin (Durham University)
* Graph Theory and Combinatorics: Jaroslav Nesetril (Charles University)
* Universal Algebra: Ross Willard (University of Waterloo)
* Approximability of CSPs: Ryan O'Donnell (CMU), Venkatesan Guruswami (CMU)

Coxeter Lectures

July 11-13, 2011
Moshe Y. Vardi, Rice University
July 11 - And Logic Begat Computer Science: When Giants Roamed the Earth
July 12 - From Philosophical to Industrial Logics
July 13 - Logic, Automata, Games, and Algorithms

July 11- 15, 2011
Workshop on Graph Homomorphisms

Organized by:
Pavol Hell (Simon Fraser University)
Claude Tardif (Royal Military College, Kingston)
Xuding Zhu (Zhejiang Normal University)

This workshop will focus on all aspects of graph homomorphisms, from those directly related to constraint satisfaction problems, such as minimum cost and list homomorphisms, versions of projectivity, and polymorphisms, to those related to basic graph theoretic notions such as colourings, tree-width and tree-depth, and those related to notions from category theory, such as adjoint functors, to those related to statistical physics such as counting homomorphisms, and study of connection matrices. The goal is to bring together the main players in all aspects of graph homomorphisms, and share views of new trends and techniques.

Invited Speakers:
Zdenek Dvorak (Charles University)
Jan Foniok (ETH Zurich)
Hamed Hatami (McGill)
Pavol Hell (SFU)
Daniel Kral (Charles University)
Andre Raspaud (University Bordeaux I)
Benoit Larose (Champlain College)
Jarik Nesetril (Charles University)
Patrice Ossona de Mendez (CAMS-CNRS, Paris)
Arash Rafiey (IDSIA, Lugano)
Mark Siggers (Kyungpook University)
Claude Tardif (Royal Military College, Kingston)
Peter Winkler (Dartmouth)
Xuding Zhu (Zhejiang Normal University)

August 2 - 6, 2011
Workshop on Algebra and CSPs

Organized by:
Libor Barto (Charles University and McMaster University)
Andrei Krokhin (Durham University)
Ross Willard (University of Waterloo)

The main goal of this workshop is to highlight the recent advances on the CSP Dichotomy Conjecture arising from the algebraic approach. It will focus on the various algebraic notions and results that have been developed in the attempts to resolve this conjecture and connected problems and will also include presentations on related algebraic topics, such as Maltsev Conditions and Tame Congruence Theory. The workshop may also include presentations on CSPs over infinite templates, quantified CSPs, and connections with logic, finite model theory, and complexity.

Invited Speakers:
Manuel Bodirsky (Ecole Polytechnique, Palaiseau)
Andrei Bulatov (Simon Fraser University)
Victor Dalmau (UPF, Barcelona)
Martin Dyer (University of Leeds)
Peter Jeavons (University of Oxford)
Vladimir Kolmogorov (University College, London)
Marcin Kozik (Jagiellonian University)
Benoit Larose (Champlain College)
Miklos Maroti (University of Szeged)
Barnaby Martin (Durham University)
Ralph McKenzie (Vanderbilt University)
Michael Pinsker (TU Vienna)
Johan Thapper (École Polytechnique)

August 12-16, 2011
Workshop on Approximability of CSPs

Organized by:
Andrei Bulatov (Simon Fraser University)
Johan Hastad (KTH, Stockholm)
Prasad Raghavendra (Microsoft Research and Georgia Tech)

The workshop will focus on the recent advances in our understanding of the approximation threshold of various CSPs, based on progress in both algorithmic techniques and methods to show tight non approximability results. The power of various convex programming relaxations for CSPs, the construction of gap instances highlighting limitations of such relaxations, and the connections of these to the complexity of approximating CSPs will be a prominent theme of the workshop. The Unique Games conjecture and results revolving around it will naturally be a centerpiece of the workshop. This workshop is expected to have a more interdisciplinary focus. In particular one of its aims is to foster a cross fertilization of ideas between the algebraic approach to characterize the tractability of CSPs and the analytic approach to characterize the approximability of CSPs, and draw parallels between the algebraic dichotomy conjecture and the Unique Games conjecture that would hopefully shed some light on both these prominent conjectures.

Invited Speakers:
Per Austrin (Toronto)
Boaz Barak (Microsoft)
Irit Dinur (Weizmann Institute)
Subhash Khot (NYU)
Andrei Krokhin (Durham)
K. Makarychev (IBM Watson)
Yury Makarychev (TTI, Chicago)
Dana Moshkovitz (MIT)
Elchanan Mossel (University of California, Berkeley)
Rishi Saket (Princeton)
David Steurer (Microsoft)
Mario Szegedy (Rutgers)
Yi Wu (IBM Almaden)

Affiliated Activity

During the week of June 20, 2011, the annual Logic in Computer Science (LICS) meeting will be held at Fields and on the campus of the University of Toronto.

Program researchers

Program Participants requesting support or office space:
All scientific events are open to the mathematical sciences community. Visitors who are interested in office space or funding are requested to apply by filling out the application form.
Fields scientific programs are devoted to research in the mathematical sciences, and enhanced graduate and post-doctoral training opportunities. Part of the mandate of the Institute is to broaden and enlarge the community, and to encourage the participation of women and members of visible minority groups in our scientific programs.

For additional information contact thematic(PUT_AT_SIGN_HERE)

Back to Top