Workshop on Approximability of CSPs
Description
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.
Schedule
09:20 to 09:30 |
Welcome and Introductions
Location: |
09:30 to 10:30 |
Rishi Saket, Princeton University Location: |
10:30 to 11:00 |
Coffee Break
|
11:00 to 12:00 |
Konstantin Makarychev, Northwestern University Location: |
12:00 to 14:00 |
Lunch Break
|
14:00 to 15:00 |
Yi Wu, IBM Almaden Research Center Location: |
15:00 to 15:30 |
Coffee Break
|
15:30 to 16:00 |
Aravindan Vijayaraghavan, Princeton University Location: |
17:30 to 18:30 |
Reception
|
09:30 to 10:30 |
Elchanan Mossel, University of California Berkeley Location: |
10:30 to 11:00 |
Coffee Break
|
11:00 to 12:00 |
Gábor Kun, Rényi Institute Location: |
12:00 to 14:00 |
Lunch Break
|
14:00 to 15:00 |
The Grothendieck Constant is Strictly Smaller than Krivine's Bound
Yury Makarychev, Toyota Technological Institute at Chicago Location: |
15:00 to 15:30 |
Coffee Break
|
09:30 to 10:30 |
Andrei Krokhin, Durham University Location: |
10:30 to 11:00 |
Coffee Break
|
11:00 to 12:00 |
Making the long code shorter, with applications to the unique games conjecture
Boaz Barak, Microsoft Research Location: |
12:00 to 14:00 |
Lunch Break
|
09:30 to 10:30 |
Per Austrin, University of Toronto Location: |
10:30 to 11:00 |
Coffee Break
|
11:00 to 12:00 |
Andrei Bulatov, Simon Fraser University Location: |
12:00 to 14:00 |
Lunch Break
|
14:00 to 15:00 |
Dana Moshkovitz, Massachusetts Institute of Technology Location: |
15:00 to 15:30 |
Coffee Break
|
15:30 to 16:00 |
Globally Constrained CSP
Ning Tan, Georgia Institute of Technology Location: |
09:30 to 10:30 |
No Title Specified
Libor Barto, McMaster University Location: |
10:30 to 11:00 |
Coffee Break
|
11:00 to 12:00 |
David Steurer, Microsoft Research Location: |
12:00 to 14:00 |
Lunch Break
|