Title: Monogamy of entanglement and convex geometry

Abstract: The SoS (sum of squares) hierarchy is a flexible algorithm that can be used to optimize polynomials and to test whether a quantum state is entangled or separable.  (Remarkably, these two problems are nearly isomorphic.)  These questions lie at the boundary of P, NP and the unique games conjecture, but it is in general open how well the SoS algorithm performs.   I will discuss how ideas from quantum information (the “monogamy” property of entanglement) can be used to understand this algorithm.  Then I will describe an alternate algorithm that relies on apparently different tools from convex geometry that achieves similar performance.  This is an example of a series of remarkable parallels between SoS algorithms and simpler algorithms that exhaustively search over carefully chosen sets.  Finally, I will describe known limitations on SoS algorithms for these problems.