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 
                             | 
      

