Abstract
We will have an in-depth look at pseudocalibration, a new technique for understanding the power of convex relaxations for average-case/planted problems.
Examples of such problems include planted constraint satisfaction, planted clique, component analysis problems, the stochastic block model, densest-k-subgraph, and more.
While it originated in work of Barak et al. on tight Sum-of-Squares lower bounds for the planted clique problem, the technique is applicable to any average-case problem which is nice enough to allow Fourier analysis of the underlying probability distribution.
In addition to the original work on planted clique, pseudocalibration has already yielded tight Sum of Squares lower bounds for refutation of random constraint satisfaction problems (Kothari et al) and computationally hard variants of principal component analysis (Hopkins et al.), and a structure theorem characterizing Sum of Squares algorithms for planted problems in terms of simpler "low-degree" spectral algorithms (Hopkins et al.).
There are even indications that pseudocalibration could be used to analyze more classes of convex programs than the Sum of Squares semidefinite programs (for example, Sherali-Adams linear programs or liner/semidefinite extended formulations), and that even stronger structure theorems may be in reach via the pseudocalibration technique.
In two tutorial-style talks we will review these recent results, discuss the basics of pseudocalibration, and, time-permitting, discuss the mathematical techniques which go into proving these "pseudocalibrated" theorems.