April 25, 2014
July -August, 2011
Thematic Program on the Mathematics of Constraint Satisfaction

August 12-16, 2011
Workshop on Approximability of CSPs

Organized by Andrei Bulatov (Simon Fraser University)
Johan Hästad (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.

Workshop Schedule (talk titles and abstracts)

Friday August 12 - *Bahen Centre Rm. 1230*
9:20 - 9:30 Welcome and Introduction
Workshop Organizers
9:30 - 10:30 Rishi Saket (Princeton University)
Some optimal geometric inapproximability results without assuming UGC
10:30 - 11:00 Coffee Break
11:00 - 12:00 Konstantin Makarychev (IBM T.J. Watson Research Center)
How to Play Unique Games Against a Semi-Random Adversary
12:00 - 2:00 Lunch Break
2:00 - 3:00 Yi Wu (IBM Almaden Research Center)
On the hardness of pricing loss leaders
3:00 - 3:30 Coffee Break
3:30 - 4:00 Aravindan Vijayaraghavan (Princeton University)
On the Densest k-Subgraph problem
5:30 - 6:30 Reception
Fields Atrium - cash bar
Saturday August 13
9:30 - 10:30 Elchanan Mossel (University of California, Berkeley)
Tests of deviation from dictatorship
10:30 - 11:00 Coffee Break
11:00 - 12:00 Gabor Kun (Institute for Advanced Study)
Linear programming robustly decides width-1 CSP's
12:00 - 2:00 Lunch Break
2:00 - 3:00 Yury Makarychev (Toyota Technological Institute at Chicago)
The Grothendieck Constant is Strictly Smaller than Krivine's Bound
3:00 - 3:30 Coffee Break
Sunday August 14
9:30 - 10:30 Andrei Krokhin (Durham University)
Robust algorithms for CSPs
10:30 - 11:00 Coffee Break
11:00 - 12:00 Boaz Barak (Microsoft Corporation)
Making the long code shorter, with applications to the unique games conjecture
12:00 - 2:00 Lunch Break
Monday August 15 - REVISED
9:30 - 10:30 Per Austrin (University of Toronto)
On the usefulness of predicates
10:30 - 11:00 Coffee Break
11:00 - 12:00 Andrei Bulatov (Simon Fraser University)
Approximate counting
12:00 - 2:00 Lunch Break
2:00 - 3:00 Dana Moshkovitz (Massachusetts Institute of Technology)
The Sliding Scale Conjecture From Intersecting Curves
3:00 - 3:30 Coffee Break
3:30 - 4:00 Ning Tan (Georgia Institute of Technology)
Globally Constrained CSP
Tuesday August 16 - REVISED
9:30 - 10:30 Libor Barto (McMaster University)
10:30 - 11:00 Coffee Break
11:00 - 12:00 David Steurer (Microsoft Research New England)
Subexponential Algorithms for Unique Games and Related Problems


Confirmed Participants

Full Name University/Affiliation
Andrews, Rob (no affiliation)
Austrin, Per University of Toronto
Barak, Boaz Microsoft Corporation
Barto, Libor McMaster University
Benabbas, Siavosh University of Toronto
Bulatov, Andrei Simon Fraser University
Bulín, Jakub Charles University in Prague
Foniok, Jan Queen's University
Ghasemloo, Kaveh University of Toronto
Hĺstad, Johan KTH - Royal Institute of Technology
Horowitz, Jonah McMaster University
Huang, Sangxia KTH - Royal Institute of Technology
Kazda, Alexandr Charles University in Prague
Koiran, Pascal ENS Lyon
Kozik, Marcin Jagiellonian University
Krokhin, Andrei Durham University
Kun, Gabor Institute for Advanced Study
Laekhanukit, Bundit McGill University
Le, Dai Tri Man University of Toronto
Makarychev, Konstantin IBM T.J. Watson Research Center
Makarychev, Yury Toyota Technological Institute at Chicago
Marecek, Jakub The University of Nottingham
Martin, Barnaby Durham University
Mayr, Peter Centro de Álgebra da Universidade de Lisboa
McKenzie, Ralph Vanderbilt University
Moshkovitz, Dana Massachusetts Institute of Technology
Mossel, Elchanan University of California, Berkeley
Popat, Preyas New York University
Pressman, Irwin Carleton University
Qin, Teng Ecole Normale Superieure de Paris
Raghavendra, Prasad Georgia Institute of Technology
Saket, Rishi Princeton University
Shinkar, Igor The Weizmann Institute of Science
Stacho, Juraj University of Haifa
Steurer, David Microsoft Research New England
Tamaki, Suguru Kyoto University
Tan, Ning Georgia Institute of Technology
Thapper, Johan École Polytechnique
Valeriote, Matthew McMaster University
Vijayaraghavan, Aravindan Princeton University
Willard, Ross University of Waterloo
Wu, Yi IBM Almaden Research Center


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(at)

Back to Top