Proofs, beliefs and algorithms through the lens of Sum of Squares
Excerpt
Boaz Barak and David Steurer
Boaz Barak and David Steurer
work in progress (Fall 2016)
A random graph with a hidden clique. The sum-of-squares algorithm maintains a set of beliefs about which vertices belong to the hidden clique. Despite learning no new information, as we invest more computation time, the algorithm reduces uncertainty in the beliefs by making them consistent with increasingly powerful proof systems. Initially the beliefs have maximum uncertainty and correspond to the uniform distribution but they eventually converge on the correct hidden clique (red edges).
Seminars & workshops
- SOS seminar by Pravesh Kothari and David Steurer at Princeton University, Fall 2016
- SOS seminar by Boaz Barak and Pablo Parrilo at Harvard University and MIT, Fall 2016
- Four-day winter school in UC San Diego on the sum of squares algorithm January 3-6. See the web page for registration and more information.