The computational complexity of convex bodies

For convex bodies associated to many interesting and important questions, deciding whether a given point is a member of the body is computationally hard. Thus, one looks for an approximating body for which deciding membership is computationally feasible. In this talk, I will discuss using polytopes, projections of polytopes, and sections of the cone of positive semidefinite quadratic forms to approximate convex bodies. I will discuss in particular the case where the set approximated is the Traveling Salesman Polytope.