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.
Schedule:
-
1:00-1:45: Pablo Parrilo: Introduction to Sum of Squares.
Applications in optimization, dynamical systems, and beyond. Symmetry reduction and flag algebras.
slides
-
1:45-2:30: Tselil Schramm: SOS and spectral algorithms. CSPs and random polynomials. Algorithmic speedups.
slides
-
2:30-3:00: Break
-
3:00-3:45 : Sam
Hopkins: Duality, Bayesian pseudo-expectations and
rounding. Planted clique problem.
slides
-
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:
-
Harvard/MIT course:
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,
arXiv:1404.5236
-
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,
arXiv:1604.03084
-
Semidefinite programming relaxations for semialgebraic problems.
P.A. Parrilo, Mathematical Programming Ser. B, Vol. 96,
No.2, pp. 293-320, 2003.
pdf.
-
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors.
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer,
arXiv:1512.02337