Open Collections

Sum of squares and computational bayesanism

Banff International Research Station for Mathematical Innovation and Discovery

The Sum of Squares (SOS) algorithm (Parrilo, Lasserre) is a powerful convex programming hierarchy that captures many of the best-known techniques for various algorithmic problems. In this talk I will discuss how we can interpret the state of this algorithm as modelling the beliefs of a computationally bounded agent about some unknown quantity via Bayesian "pseudo probabilities" and moreover how this viewpoint helps in obtaining new upper and lower bounds for this algorithm. In particular I will outline how we can use this approach to show that the SOS algorithm cannot distinguish in polynomial-time between a random Erdos-Renyi G(n,1/2) graph and such a graph in which a clique of size n^{1/2-epsilon} was planted in for every epsilon > 0. I will also show how the approach can be used to connect the Best Separable State problem (also known as the QMA(2) verification probability problem) of finding a non-entangled state maximizing a certain measurement to questions related to the log-rank conjecture from communication complexity. We use this connection, together with the techniques underlying Lovett's bounds on the log rank question question to obtain a better-than-brute-force algorithm for the Best Separable State problem. The talk will be based on joint works with Sam Hopkins, Jon Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin and David Steurer. It will be a high level talk assuming no prior knowledge on SOS. If there is interest, I (or my co authors) could offer talks with the full proofs and more details in an afternoon talk.

Mathematics; Computer science; Theoretical computer science

video/mp4

Author affiliation: Harvard

2017-03-07

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/60819

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/