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(PUT_AT_SIGN_HERE)fields.utoronto.ca

Back to Top

THEMATIC PROGRAMS

August 12-16, 2011 Workshop on Approximability of CSPs

OVERVIEW

Workshop Schedule (talk titles and abstracts)

Confirmed Participants

Program Researchers

August 12-16, 2011
Workshop on Approximability of CSPs