Boaz Barak: Computational Bayesianism, Sums of Squares, and Unicorns
Tuesday, September 13, 2016 - 4:00pm to 5:00pm
Refreshments:
Light Refreshments at 3:50pm
Location:
Patil/Kiva G449
Speaker:
Boaz Barak, Harvard Paulson School
Seminar group:
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.