CATS-Oct-2-2015
Title
Lassere Hierarchy
Speaker
Pan Xu
Abstract
Lassere Hierarchy is an important tool for systematically reducing the size of a feasible polytope in many optimization problems. This tool has been used extensively in the last decade in a variety of approximation algorithms. In this talk, we will go over a beautiful survey written by Thomas Rothvoss on this subject(http://www.math.washington.edu/~rothvoss/lecturenotes/lasserresurvey.pdf). This is a continuation of the two-part talk. In this second part, we will have a look at some of the applications(e.g. Matching and Max Cut) and the power of this tool. This talk is a good mix of convex optimization and algorithmic techniques with very little pre-requisites needed.