Vitaly Feldman: Lower bounds against convex relaxations via the statistical query complexity

Abstract: 

In this talk I'll show how algorithms for convex optimization can be
used to derive lower bounds against general convex relaxations for
constraint satisfaction problems. This technique relies on several
recent advances in understanding of statistical query* (SQ)
complexity:
1. A notion of SQ dimension of a problem that lower bounds the SQ complexity
2. Lower bounds on the SQ dimension of constraint satisfaction problems
3. SQ algorithms for stochastic convex optimization.
I'll overview these results and give some of their additional applications.

* Statistical query algorithms (Kearns, 1993) are algorithms that
instead of random samples from an input distribution D over a domain
X, have access to a SQ oracle for D. Given a real-valued query
function g over X, the oracle returns an estimate of the expectation
of g on a sample chosen randomly from D.
Based on joint works with C. Guzman, W. Perkins and S. Vempala.