This website hosts informal notes and bibliographic references from the 2018 workshop on algorithms and statistical inference, organized by Cris Moore.
Photographer: Florent Krzakala
Not pictured: Afonso Bandeira, Boaz Barak, Cris Moore, Dana Randall, Jiaming Xu, Xiaoran Yan
This does not aim to be a complete bibliography of works on Sum of Squares methods in noisy inference. However, if you find it useful and wish there were such bibliography, send one of us an email. Perhaps we will get around to it.
Grigoriev’s 3XOR lower bound. Theoretical Computer Science. pdf
Schoenebeck’s rediscovery of the same. FOCS '08. pdf
Kothari, Mori, O’Donnell, Witmer. Sum of squares lower bounds for refuting any CSP. STOC '17 Most general known SoS lower bounds for the random CSP refutation problem. Construction of pseudoexpectation is very similar to the pseudocalibration construction. arxiv. Lower bound side of the running time vs clause density tradeoff curve.
Allen, O’Donnell, Witmer. How to refute a random csp. FOCS '15. arxiv
Raghavendra, Rao, Schramm. Strongly refuting random CSPs below the spectral threshold. STOC '17. Together with Allen-O’Donnell-Witmer paper, gives tradeoff among SoS degree, clause density, refutation strength for every random constant-arity CSP. arxiv. Algorithm side of the running time vs clause density tradeoff curve.
Meka, Potechin, Wigderson. Sum-of-squares lower bounds for planted clique. STOC '15. First paper to show that polynomial-time SoS algorithms to cannot find sub-polynomial size cliques. arxiv
Deshpande, Montanari. Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems. Improved analysis of construction of Meka, Potechin, and Wigderson for SoS degree 4. arxiv
Hopkins, Kothari, Potechin, Raghavendra, Schramm. On the integrality gap of degree-4 sum of squares for planted clique. SODA '16. First nearly-tight sum of squares lower bout for degree-4 SoS. arxiv 1 (Hopkins, Kothari, Potechin version) arxiv 2 (Raghavendra, Schramm version).
Barak, Hopkins, Kelner, Kothari, Moitra, Potechin. A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. FOCS '16. Introduced pseudocalibration as a tool for SoS lower bounds. arxiv. Source of “pseudocalibrated pseudodistribution” construction from Tselil’s workshop talk.
Hopkins, Kothari, Potechin, Raghavendra, Schramm, Steurer. The power of SoS for detecting hidden structures. FOCS '17. Contains nearly-tight SoS lower bounds for spiked tensors and sparse pca, and the spectral-to-sos argument. arxiv. Source of spectral vs SoS arguments in Tselil’s workshop talk.
Hopkins, Shi, Steurer. Tensor principal component analysis via sum of squares proofs. COLT '15. Nearly tight degree 4 SoS algorithms and lower bounds. arxiv. Source of SoS proof from Sam’s workshop talk.
Hopkins, Kothari, Potechin, Raghavendra, Schramm, Steurer. The power of SoS for detecting hidden structures. FOCS '17. Contains among other things a nearly-tight tensor pca lower bound for high degree SoS via pseudocalibration. arxiv
Raghavendra, Rao, Schramm. Strongly refuting random CSPs below the spectral threshold. STOC '17. Gives a nearly-tight computation-time vs noise tradeoff via high-degree SoS. arxiv
Notes by Bandeira, Perry, and Wein arxiv
Exercises from Florent’s EPFL course overleaf
Krzakala, Xu, Zdeborova. Mutual Information in Rank-One Matrix Estimation. arxiv. Florent’s talk.
El Alaoui, Krzakala. Estimation in the Spiked Wigner Model: A Short Proof of the Replica Formula. arxiv. Ahmed’s talk.
First appeared in the following two papers of Franz and Parisi to study the relaxation time of dynamics in spin glasses:
Recipes for metastable states in spin glasses arxiv
Effective potential in glassy systems: theory and simulations arxiv
On the limit of the normalized free energy, and information-theoretic limits of spiked-matrix estimation:
On fluctuations in the free energy and the likelihood ratio in the estimation-is-impossible regime. This gives the limits of detection (distinguishing the null from the planted).
Mostly drawn from this paper: https://arxiv.org/abs/1611.00814