Hierarchies, Extended Formulations and Matrix-Analytic Techniques


Simons Institute for the Theory of Computing

Start Date:

End Date:

Deadline for paper submissions:

Deadline for participant registration:

Type

Workshops

Location

121 Calvin Lab #2190 UC Berkeley

United States

Start Date:

End Date:

Location

United States

Type

Workshops

Deadline for paper submissions:

Deadline for participant registration:


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.