Fall 2017

Hierarchies, Extended Formulations and Matrix-Analytic Techniques

Nov. 6Nov. 9, 2017

Add to Calendar


Prasad Raghavendra (UC Berkeley; chair), Nick Harvey (University of British Columbia), Pablo Parrilo (Massachusetts Institute of Technology), Sebastian Pokutta (Georgia Institute of Technology), Cynthia Vinzant (North Carolina State University)

An important development in the area of convex relaxations has been the introduction of systematic ways of strengthening them by lift-and-project techniques. This leads to several hierarchies of LP/SDP relaxations: Lovasz-Schrijver, Sherali-Adams and Sum of Squares (also known as the Lasserre hierarchy). The benefits and limitations of these hierarchies have been studied extensively over the last decade. Recently, strong negative results have been obtained, not only for specific hierarchies but even for the more general notion of extended formulations. In this workshop we investigate the power and limitations of LP/SDP hierarchies as well as general extended formulations, and their ties to convex algebraic geometry. We also explore tools and concepts from matrix analysis with strong connections to SDP formulations: matrix concentration, matrix multiplicative weight updates, and various notions of matrix rank. Finally, the workshop will cover related areas where these kinds of techniques are employed: sparsification, discrepancy and hyperbolic/real stable polynomials.

Visit the schedule page link above for the archived videos.

Invited Participants: 

Amir Ali Ahmadi (Princeton University), Nima Anari Ahmadipouranari (Stanford University), Farid Alizadeh (Rutgers University), Jason Altschuler (MIT), Kyriakos Axiotis (MIT), Afonso Bandeira (Courant Institute of Mathematical Sciences, NYU), Nikhil Bansal (Eindhoven University of Technology), Greg Blekherman (Georgia Institute of Technology), Manuel Blum (Carnegie Mellon University), Lenore Blum (Carnegie Mellon University), Deeparnab Chakrabarty (Dartmouth College), Parinya Chalermsook (Aalto University), Moses Charikar (Stanford University), Ken Clarkson (IBM Almaden), Michael Cohen (MIT), Jelena Diakonikolas (Boston University), Reza Eghbali (University of Washington), Friedrich Eisenbrand (École Polytechnique Fédérale de Lausann), Alina Ene (Boston University), Hamza Fawzi (University of Cambridge), Maryam Fazel (University of Washington), Sam Fiorini (Université Libre de Bruxelles), Shashwat Garg (TU Eindhoven), Mika Göös (University of Toronto), Ben Grimmer (Cornell University), Swati Gupta (MIT), Venkat Guruswami (Carnegie Mellon University), Leonid Gurvits (City University of New York), Georgina Hall (Princeton University), Moritz Hardt (UC Berkeley), Robert Hildebrand (IBM T.J. Watson Research Center), Rebecca Hoberg (University of Washington), Dorit Hochbaum (UC Berkeley), Samuel Hopkins (Cornell University), Tony Huynh (Université Libre de Bruxelles), Volker Kaibel (Otto-von-Guericke-Universität Magdeburg), Ravi Kannan (Microsoft Research India), Samir Khuller (University of Maryland), Fatma Kılınç-Karzan (Carnegie Mellon University), Alexandra Kolla (University of Illinois at Urbana-Champaign), Matthias Köppe (University of California, Davis), Pravesh Kothari (Princeton University), Rasmus Kyng (Yale University), Bundit Laekhanukit (Weizmann Institute of Science), Jean Lasserre (CNRS - Toulouse), Monique Laurent (CWI Amsterdam), James Lee (University of Washington), Euiwoong Lee (Carnegie Mellon University), Jon Lee (University of Michigan), Chris Liaw (University of British Columbia), Cong Han Lim (University of Wisconsin-Madison), Mike Luby (Qualcomm), Shiqian Ma (University of California, Davis), Marco Macchia (Université Libre de Bruxelles), Aleksander Mądry (MIT), Alex Makelov (MIT), Jarrod Millman (UC Berkeley), Aryan Mokhtari (University of Pennsylvania), Sarah Maria Morell (EPFL), Walaa Moursi (University of British Columbia), Seffi Naor (Technion – Israel Institute of Technology), Rad Niazadeh (Stanford University), Sasho Nikolov (University of Toronto), Ryan O'Donnell (Carnegie Mellon University), Neil Olver (Vrije Universiteit), Lorenzo Orecchia (Boston University), Shayan Oveis Gharan (University of Washington), Kostya Pashkovich (University of Waterloo), Kostya Pashkovich (University of Waterloo), Toni Pitassi (University of Toronto), Aaron Potechin (KTH Royal Institute of Technology, Aaron Potechin (Institute for Advanced Study), Daniel Vaz Ramos Vaz (Max Planck Institut für Informatik), Annie Raymond (University of Washington), Annie Raymond (University of Washington), Ben Recht (UC Berkeley), Jim Renegar (Cornell University), Alireza Rezaei (University of Washington), Thomas Rothvoß (University of Washington), Amin Saberi (Stanford University), James Saunderson (Monash University), Ludwig Schmidt (MIT), Tselil Schramm (UC Berkeley), Jonah Sherman (UC Berkeley), Aaron Sidford (Stanford University), Mohit Singh (Microsoft Research, Redmond and Georgia Institute of Technology), Nikhil Srivastava (UC Berkeley), David Steurer (Cornell University), Yue Sun (University of Washington), Ola Svensson (EPFL), Oliver Theis (University of Tartu), Rekha Thomas (University of Washington), Kim-Chuan Toh (National University of Singapore), Dimitris Tsipras (MIT), Madhur Tulsiani (Toyota Technological Institute at Chicago), Levent Tunçel (University of Waterloo), Lieven Vandenberghe (UCLA), Cynthia Vinzant (North Carolina State University), Nisheeth Kumar Vishnoi (École Polytechnique Fédérale de Lausanne), Adrian Vladu (Boston University), Jan Vondrák (Stanford University), Di Wang (UC Berkeley), David Williamson (Cornell University), Steve Wright (University of Wisconsin-Madison), Sheng Yang (University of Maryland), Yinyu Ye (Stanford University), Chenyang Yuan (MIT)