Overview
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.
Deadlines
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)fields.utoronto.ca . To receive updates on
the program please subscribe to our mailing list at www.fields.utoronto.ca/maillist
.
Details of Scientific Activities
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)
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
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)
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)
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)fields.utoronto.ca
Back to Top
