Computational Bayesianism, Sums of Squares, and UnicornsSpeaker: Boaz Barak, Harvard Paulson School
Recorded on September 13, 2016 at 17:15
About This Video
ToC Seminar Abstract: Can we make sense of quantities such as "the probability that 2^81712357 - 1 is prime" or "the probability that statement X is a logical contradiction"? More generally, can we use probabilities to quantify our "computational uncertainty" in cases where all the relevant information is given but in a computationally hard-to-extract form? In this talk we will discuss how such "pseudo probabilities" can arise from the Sum of Squares (SOS) semidefinite program (Parrilo'00, Lasserre'01). We will show how this yields an approach for showing both positive and negative results for the SOS algorithms. In particular we will present better algorithms for the tensor decomposition problem from data analysis, and stronger lower bounds for the planted clique problem. The talk will be partially based on joint works with Sam Hopkins, Jon Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin and David Steurer. I will not assume any prior knowledge on the sum of squares algorithm or semidefinite programming.