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