The following is an announcement of the summer thematic program on the
mathematics of constraint satisfaction that will be held at the Fields
Institute in Toronto this summer. One of the threads of the program is on
approximability. There will also be a workshop associated with the program
on the approximability of CSPs, that will be held during Aug 12-16, 2011,
just preceding the RANDOM/APPROX conference in Princeton.
Please circulate the announcement to any individuals who might be interested
in participating in the program, summer school, and/or any of the workshops
(details on how to apply appear below; applications by *April 15, 2011* if
possible are encouraged).
-------------------------------------------------------------------------
Fields Institute Summer Thematic Program on the Mathematics of Constraint
Satisfaction
-------------------------------------------------------------------------
Program Organisers:
Venkatesan Guruswami, Carnegie Mellon University
Pavol Hell, Simon Fraser University
Matt Valeriote, McMaster University
Ross Willard, University of Waterloo
Program Website:
http://www.fields.utoronto.ca/programs/scientific/11-12/constraint/ 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, but interested
participants are urged to apply by *April 15, 2011* if possible.
Additional Information:
For additional information on the program, please send an email to
thematic@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:
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: Venkatesan Guruswami and Ryan O'Donnell (Carnegie
Mellon)
July 11-13, 2011 The Coxeter Lectures
A series of three lectures given by Moshe Y. Vardi, Rice University
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.
Confirmed Speakers:
Zdenek Dvorak, Jan Foniok, Hossein Hajiabolhassan, Hamed Hatami, Pavol Hell,
Daniel Kral, Jan Kratochvil, Benoit Larose, Jarik Nesetril, Patrice Ossona
de Mendez, Arash Rafiey, Mark Siggers, Claude Tardif, Peter Winkler, Xuding Zhu
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.
Confirmed Speakers:
Manuel Bodirsky, Andrei Bulatov, Victor Dalmau, Martin Dyer, Peter Jeavons,
Vladimir Kolmogorov, Marcin Kozik, Gabor Kun, Benoit Larose, Miklos Maroti,
Barnaby Martin, Ralph McKenzie, Michael Pinsker
August 12 - 16, 2011 Workshop on Approximability of CSPs
Organized by:
Andrei Bulatov (Simon Fraser University),
Johan Hastad (KTH, Stockholm),
Prasad Raghavendra (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.
Confirmed Speakers:
Per Austrin, Boaz Barak, Irit Dinur, Subhash Khot, Andrei Krokhin,
Konstantin Makarychev, Yury Makarychev, Dana Moshkovitz, Elchanan Mossel,
Rishi Saket, David Steurer, Mario Szegedy, Yi Wu.
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.
Posts
