Hierarchies, Extended Formulations and Matrix-Analytic Techniques

Conference Dates: to
Deadline for paper submissions:
Deadline for participant registration:

Hierarchies, Extended Formulations and Matrix-Analytic Techniques

Conference Dates: to
Deadline for paper submissions:
Deadline for participant registration:

Simons Institute for the Theory of Computing

Type

Workshops

Location

121 Calvin Lab #2190 UC Berkeley

United States

Type

Workshops

Location

United States

Nick Harvey (University of British Columbia), Pablo Parrilo (Massachusetts Institute of Technology), Sebastian Pokutta(Georgia Institute of Technology), Prasad Raghavendra (UC Berkeley), 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.

Further details about this workshop will be posted in due course. Enquiries may be sent to the organizers at this address.