Sum of Squares: Theory and Algorithms
Mini-course given at the
49th Annual ACM Symposium on the Theory of Computing (STOC2017)
Montreal, Friday June 23 2017, 1:00PM-4:30PM.
1:00-1:45: Pablo Parrilo: Introduction to Sum of Squares.
Applications in optimization, dynamical systems, and beyond. Symmetry reduction and flag algebras.
1:45-2:30: Tselil Schramm: SOS and spectral algorithms. CSPs and random polynomials. Algorithmic speedups.
3:00-3:45 : Sam
Hopkins: Duality, Bayesian pseudo-expectations and
rounding. Planted clique problem.
3:45-4:30 : Boaz Barak: SOS and the Unique Games Conjecture. Is SOS an optimal algorithm?
slides (coming soon)
See also the related links and papers:
Proofs, beliefs and algorithms through the lens of Sum of Squares
MIT 6.256 course (2016 version):
Algebraic techniques and semidefinite optimization
G. Blekherman, P. Parrilo, R. Thomas,
Semidefinite Optimization and Convex Algebraic Geometry
MOS-SIAM Series on Optimization, Vol. 13.
Sum-of-squares proofs and the quest toward optimal algorithms.
Boaz Barak, David Steurer,
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem.
Boaz Barak, Samuel B. Hopkins, Jonathan Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin,
Semidefinite programming relaxations for semialgebraic problems.
P.A. Parrilo, Mathematical Programming Ser. B, Vol. 96,
No.2, pp. 293-320, 2003.
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors.
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer,