[CSDM] Fwd: [Theory-Read] Fwd: ORFE Colloquium: Pablo Parrilo, Nov. 25 at 4:30pm, Sherrerd Hall 101

[Avi Wigderson]

-------- Original Message --------
Subject: 	[Theory-Read] Fwd: ORFE Colloquium: Pablo Parrilo, Nov. 25 at 
4:30pm, Sherrerd Hall 101
Date: 	Wed, 19 Nov 2014 17:35:45 +0000
From: 	Philippe Rigollet <rigollet at princeton.edu>
To: 	theory-read at lists.cs.princeton.edu 
<theory-read at lists.cs.princeton.edu>



>
> === ORFE Colloquium Announcement ===
>
> DATE:  Tuesday, November 25, 2014
>
> TIME:  4:30pm
>
> LOCATION:  Sherrerd Hall room 101
>
> SPEAKER:  Pablo A. Parrilo, Dept. of Electrical Engineering & Computer
>      Science, Massachusetts Institute of Technology
>
> TITLE:   Equivariant Semidefinite Lifts and Sum-of-squares Hierarchies
>
> ABSTRACT:   A central question in optimization is to maximize (or minimize) a linear function over a given polytope P. Often, we are interested in representations of P using the positive semidefinite cone: a positive semidefinite lift (psd lift) of a polytope P is a representation of P as the projection of an affine slice of the positive semidefinite cone. Such a representation allows linear optimization problems over P to be written as semidefinite programs.
>
> In this talk we are concerned with so-called equivariant psd lifts (also known as symmetric psd lifts) which respect the symmetries of the polytope P. We present a representation-theoretic framework to study equivariant psd lifts of a certain class of symmetric polytopes known as regular orbitopes. Our main result is a structure theorem where we show that any equivariant psd lift of a regular orbitope is of "sum-of-squares" type (suitably interpreted).
>
> We use this framework to study several families of orbitopes, such as the parity polytope, the cut polytope, and regular polygons. For these, we obtain both exponential lower bounds (parity, cut) and new explicit efficient constructions (polygons).
>
> Based on joint work with Hamza Fawzi and James Saunderson.
_______________________________________________
Theory-Read mailing list
Theory-Read at lists.cs.princeton.edu
https://lists.cs.princeton.edu/mailman/listinfo/theory-read



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/csdm/attachments/20141119/d07dfe50/attachment.html>