From the stable set problem to convex algebraic geometry

Friday, November 21, 2008 - 2:45pm - 3:30pm
EE/CS 3-180
Pablo Parrilo (Massachusetts Institute of Technology)
The Lovasz theta body TH(G) is a well-known relaxation of the stable set
polytope STAB(G) that is computable using semidefinite programming. These
ideas can be extended via sum of squares techniques to other combinatorial
optimization problems, providing a natural generalization of the theta body
for general polynomial ideals. In this talk we describe these general
techniques, and characterize finite point sets whose theta body coincides
with its convex hull. This is joint work with Joao Gouveia and Rekha Thomas
(U. Washington).
MSC Code: