Title:
Separable states and their applications in computer science

Abstract:
I'll discuss how optimizing over separable states (or equivalently, estimating whether a density matrix is separable or entangled) is comparable in difficulty to many important approximation problems in classical computer science, such as estimating the 2->4 norm of a
matrix, or estimating the minimum expansion of small subsets of a graph. These connections yield new (classical) algorithms and lower bounds for these approximation problems, and may also yield new classes of interesting quantum states by adapting results from classical computer science.

Joint work with Boaz Barak, Fernando Brandao, Jon Kelner, David Steurer and Yuan Zhou (STOC 2012, arXiv:1205.4484).