Hierarchies, Extended Formulations and Matrix-Analytic Techniques
Organizers:
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.
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), Vijay Bhattiprolu (Carnegie Mellon University), Greg Blekherman (Georgia Institute of Technology), Charles Carlson (University of Illinois Urbana-Champaign), Ken Clarkson (IBM Almaden), Michael Cohen (MIT), Jelena Diakonikolas (Boston University), Reza Eghbali (University of Washington), Hamza Fawzi (University of Cambridge), Maryam Fazel (University of Washington), Sam Fiorini (Université Libre de Bruxelles), Mika Göös (University of Toronto), Ben Grimmer (Cornell University), Swati Gupta (MIT), Venkat Guruswami (Carnegie Mellon University), Georgina Hall (Princeton University), Nick Harvey (University of British Columbia), Robert Hildebrand (IBM T.J. Watson Research Center), Rebecca Hoberg (University of Washington), Samuel Hopkins (Cornell University), Volker Kaibel (Otto-von-Guericke-Universität Magdeburg), Samir Khuller (University of Maryland), Alexandra Kolla (University of Illinois at Urbana-Champaign), Matthias Köppe (University of California, Davis), Pravesh Kothari (Princeton 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), Chris Liaw (University of British Columbia), Cong Han Lim (University of Wisconsin-Madison), Marco Macchia (Université Libre de Bruxelles), Aleksander Mądry (MIT), Alex Makelov (MIT), Aryan Mokhtari (University of Pennsylvania), Andrea Montanari (Stanford University), Sarah Maria Morell (EPFL), Walaa Moursi (University of British Columbia), Seffi Naor (Technion – Israel Institute of Technology), Huy Nguyen (Northeastern University), Sasho Nikolov (University of Toronto), Ryan O'Donnell (Carnegie Mellon University), Neil Olver (Vrije Universiteit), Lorenzo Orecchia (Boston University), Pablo Parrilo (MIT), Kostya Pashkovich (University of Waterloo), Toni Pitassi (University of Toronto), Sebastian Pokutta (Georgia Institute of Technology), Aaron Potechin (Institute for Advanced Study), Prasad Raghavendra (UC Berkeley) Daniel Ramos Vaz (Max Planck Institut für Informatik), Annie Raymond (University of Washington), Ben Recht (UC Berkeley), Jim Renegar (Cornell University), Thomas Rothvoß (University of Washington), James Saunderson (Monash University), Ludwig Schmidt (MIT), Tselil Schramm (UC Berkeley), Mohit Singh (Microsoft Research, Redmond and Georgia Institute of Technology), David Steurer (Cornell University), 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), Soledad Villar (NYU), Cynthia Vinzant (North Carolina State University), Jan Vondrák (Stanford University), David Williamson (Cornell University), Steve Wright (University of Wisconsin-Madison), Chenyang Yuan (MIT)
