Santa Fe Workshop on Limits to Inference in Networks and Noisy Data, 2018

This website hosts informal notes and bibliographic references from the 2018 workshop on algorithms and statistical inference, organized by Cris Moore.

group photo
Photographer: Florent Krzakala
Not pictured: Afonso Bandeira, Boaz Barak, Cris Moore, Dana Randall, Jiaming Xu, Xiaoran Yan

Sum of Squares Algorithms and Noisy Inference Bibliography

This is an informal bibliography of works referenced in a series of talks given by Boaz Barak, Sam Hopkins, and Tselil Schramm given at the workshop on noisy inference at the Santa Fe Institute.

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.

Refutation of random CSPs

Lower bounds

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.

Algorithms

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.

Planted Clique (the ur-problem for pseudocalibration)

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.

Pseudocalibration Beyond Planted Clique

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.

Tensor PCA/Spiked Tensors

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

Replica and Cavity Methods

Notes by Bandeira, Perry, and Wein arxiv

Exercises from Florent’s EPFL course overleaf

Interpolation (Florent and Ahmed’s talks)

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.

Krzakala, Zdeborova. Short introduction to replica method and interpolation, in lecture notes. part 1 part 2

Background and History of the Franz-Parisi potential

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

and

Effective potential in glassy systems: theory and simulations arxiv

Other papers on the same topic:

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).

Rigorous free energy computations in sparse models (Will’s talk)

Mostly drawn from this paper: https://arxiv.org/abs/1611.00814