Videos

From the stable set problem to convex algebraic geometry

Presenter
November 21, 2008
Keywords:
  • Semidefinite programming
MSC:
  • 90C22
Abstract
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).