Theory of Computing Seminar

In this talk I'll show how algorithms for convex optimization can be used to derive lower bounds against general convex relaxations for well-studied constraint satisfaction problems. This technique relies on several recent advances in understanding of statistical query (SQ) algorithms*:

1. A notion of SQ dimension of a problem that lower bounds the SQ complexity of the problem.

2. Analysis of the SQ dimension of a class 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.