# Computational Bayesianism, Sums of Squares, and Unicorns

Speaker:**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.

*457*times

##### Note: to download, right-click on the links below and choose "Save file as".

HD, MP4 FormatHD, WebM Format

SD, MP4 Format

SD, WebM Format

No comments were found for this video. Be the first!