Semi-definite programming based algorithms can often be seen as natural generalizations or powerful variants of spectral methods. Recent work on semi-definite programming hierarchies has exposed a close connection between the spectrum of a graph and the efficacy of SDP hierarchies for solving various problems on it. Moreover, these developments have demonstrated the close ties between graph partitioning problems and the Unique Games Conjecture.

This workshop aims to bring together researchers interested in the power of semidefinite programming hierarchies in approximation algorithms on the one hand, and in spectral graph partitioning algorithms with theoretical guarantees on the other.

Enquiries may be sent to the organizers workshop_spectral1 [at] lists.simons.berkeley.edu (at this address.)

Invited Participants

Animashree Anandkumar (UC Irvine), Sanjeev Arora (Princeton University), Boaz Barak (Microsoft Research New England), Peter Bartlett (UC Berkeley), Steve Butler (Iowa State University), Venkat Chandrasekaran (California Institute of Technology), Moses Charikar (Princeton University), Fan Chung (UC San Diego), Mihai Cucuringu (UCLA), Alexandre d'Aspremont (CNRS - École Normale Superieure Paris), Laurent El Ghaoui (UC Berkeley), Maryam Fazel (University of Washington), Rong Ge (Microsoft Research), Shayan Oveis Gharan (UC Berkeley), Aram Harrow (Massachusetts Institute of Technology), Dorit Hochbaum (UC Berkeley), Samuel Hopkins (Cornell University), Sorin Istrail (Brown University), Michael Jordan (UC Berkeley), Ravi Kannan (Microsoft Research India), Jonathan Kelner (Massachusetts Institute of Technology), Alexandra Kolla (University of Illinois, Urbana-Champaign), Ioannis Koutis (University of Puerto Rico), Tsz Chiu Kwok (Chinese University of Hong Kong), Bundit Laekhanukit (McGill University), Lap Chi Lau (University of Waterloo), James Lee (University of Washington), Yin Tat Lee (Massachusetts Institute of Technology), Jerry Li (Massachusetts Institute of Technology), Elon Lindenstrauss (Hebrew University of Jerusalem), Nati Linial (Hebrew University of Jerusalem), Konstantin Makarychev (Microsoft Research), Jitendra Malik (UC Berkeley), Adam Marcus (Yale University), Gary Miller (Carnegie Mellon University), Ankur Moitra (Massachusetts Institute of Technology), Miguel Navascués Cobo (Universitat Autònoma de Barcelona), Huy Nguyen (Princeton University), Jakub Pachocki (Carnegie Mellon University), Pablo Parrilo (Massachusetts Institute of Technology), Aaron Potechin (Massachusetts Institute of Technology), Prasad Raghavendra (UC Berkeley), Satish Rao (UC Berkeley), Benjamin Recht (UC Berkeley), Margaret Reid-Miller (Carnegie Mellon University), James Renegar (Cornell University), Marie-Françoise Roy (Universite de Rennes), Sushant Sachdeva (Yale University), Leonard Schulman (California Institute of Technology), Jonathan Shi (Cornell University), Aaron Sidford (Massachusetts Institute of Technology), Ali Sinop (Institute for Advanced Study, Princeton), David Steurer (Cornell University), Bernd Sturmfels (UC Berkeley), He Sun (Max-Planck-Institut für Informatik), Li-Yang Tan (Columbia University), Rekha Thomas (University of Washington), Luca Trevisan (UC Berkeley), Madhur Tulsiani (Toyota Technological Institute at Chicago), Levent Tunçel (University of Waterloo), Frank Vallentin (University of Cologne), Santosh Vempala (Georgia Institute of Technology), Nisheeth Vishnoi (École Polytechnique Fédérale de Lausanne), Stephanie Wehner (National University of Singapore), Shen Chen Xu (Carnegie Mellon University).