Fetching the paper…
Reading the bibliography…
In these notes we describe heuristics to predict computational-to-statistical gaps in certain statistical problems.
A limit theorem for multidimensional galton-watson processes
Harry Kesten and Bernt P Stigum · 1966
Earlier work this paper cites.
Reducibility among combinatorial problems
R. M. Karp · 1972
Earlier work this paper cites.
Solution of ‘solvable model of a spin glass’
David J Thouless, Philip W Anderson, and Robert G Palmer · 1977
Earlier work this paper cites.
On the shannon capacity of a graph
L. Lovasz · 1979
Earlier work this paper cites.
Infinite number of order parameters for spin-glasses
Giorgio Parisi · 1979
Earlier work this paper cites.
Exact results and critical properties of the ising model with competing interactions
Hidetoshi Nishimori · 1980
Earlier work this paper cites.
Internal energy, specific heat and correlation function of the bond-random ising model
Hidetoshi Nishimori · 1981
Earlier work this paper cites.
Stochastic blockmodels: First steps
P. W. Holland, K. Blackmond Laskey, and S. Leinhardt · 1983
Earlier work this paper cites.
SK model: The replica solution without replicas
Marc Mézard, Giorgio Parisi, and MA Virasoro · 1986
Earlier work this paper cites.
Fusion, propagation, and structuring in belief networks
Judea Pearl · 1986
Earlier work this paper cites.
An approach to obtaining global extremums in polynomial mathematical programming problems
N. Shor · 1987
Earlier work this paper cites.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefine programming
M. X. Goemans and D. P. Williamson · 1995
Earlier work this paper cites.
Finding a large hidden clique in a random graph
N. Alon, M. Krivelevich, and B. Sudakov · 1998
Earlier work this paper cites.
Squared functional systems and optimization problems
Y. Nesterov · 2000
Earlier work this paper cites.
Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization
P. A. Parrilo · 2000
Earlier work this paper cites.
Global optimization with polynomials and the problem of moments
J. B. Lassere · 2001
Earlier work this paper cites.
Statistical physics of spin glasses and information processing: an introduction
Hidetoshi Nishimori · 2001
Earlier work this paper cites.
On the power of unique 2-prover 1-round games
S. Khot · 2002
Earlier work this paper cites.
Random Fields and Geometry
R. J. Adler and J. E. Taylor · 2007
Earlier work this paper cites.
Optimal algorithms and inapproximability results for every CSP?
P. Raghavendra · 2008
Earlier work this paper cites.
Message-passing algorithms for compressed sensing
David L Donoho, Arian Maleki, and Andrea Montanari · 2009
Earlier work this paper cites.
Information, physics, and computation
Marc Mezard and Andrea Montanari · 2009
Earlier work this paper cites.
On the unique games conjecture (invited survey)
S. Khot · 2010
Earlier work this paper cites.
The dynamics of message passing on dense graphs, with applications to compressed sensing
Mohsen Bayati and Andrea Montanari · 2011
Earlier work this paper cites.
Inference and phase transitions in the detection of modules in sparse networks
Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová · 2011
Earlier work this paper cites.
Angular synchronization by eigenvectors and semidefinite programming
A. Singer · 2011
Cited alongside, same era.
An iterative construction of solutions of the tap equations for the sherrington-kirkpatrick model
Erwin Bolthausen · 2012
Cited alongside, same era.
Optimal detection of sparse principal components in high dimension
Q. Berthet and P. Rigollet · 2012
Cited alongside, same era.
Iterative reconstruction of rank-one matrices in noise
Alyson K Fletcher and Sundeep Rangan · 2012
Cited alongside, same era.
Stochastic block models and reconstruction
Elchanan Mossel, Joe Neeman, and Allan Sly · 2012
Cited alongside, same era.
Random matrices and complexity of spin glasses
A nearly tight sum-of-squares lower bound for the planted clique problem
B. Barak, S. B. Hopkins, J. Kelner, P. K. Kothari, A. Moitra, and A. Potechin · 2016
Later among the works it cites.
Noisy tensor completion via the sum-of-squares hierarchy
Boaz Barak and Ankur Moitra · 2016
Later among the works it cites.
Information-theoretic thresholds for community detection in sparse networks
Jess Banks, Cristopher Moore, Joe Neeman, and Praneeth Netrapalli · 2016
Later among the works it cites.
The non-convex burer-monteiro approach works on smooth semidefinite programs
N. Boumal, V. Voroninski, and A. S. Bandeira · 2016
Later among the works it cites.
Information-theoretic thresholds from the cavity method
Amin Coja-Oghlan, Florent Krzakala, Will Perkins, and Lenka Zdeborova · 2016
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Antonio Auffinger, Gérard Ben Arous, and Jiří Černỳ · 2013
Cited alongside, same era.
Rounding sum-of-squares relaxations
B. Barak, J. Kelner, and D. Steurer · 2013
Cited alongside, same era.
Complexity theoretic lower bounds for sparse principal component detection
Q. Berthet and P. Rigollet · 2013
Cited alongside, same era.
State evolution for general approximate message passing algorithms, with applications to spatial coupling
Adel Javanmard and Andrea Montanari · 2013
Cited alongside, same era.
A proof of the block model threshold conjecture
Elchanan Mossel, Joe Neeman, and Allan Sly · 2013
Cited alongside, same era.
Computational barriers in minimax submatrix detection
Z. Ma and Y. Wu · 2013
Cited alongside, same era.
Sum-of-squares proofs and the quest toward optimal algorithms
B. Barak and D. Steurer · 2014
Cited alongside, same era.
Asymptotic mutual information for the binary stochastic block model
Yash Deshpande, Emmanuel Abbe, and Andrea Montanari · 2016
Later among the works it cites.
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
Samuel B Hopkins, Tselil Schramm, Jonathan Shi, and David Steurer · 2016
Later among the works it cites.
Phase transitions in semidefinite relaxations
Adel Javanmard, Andrea Montanari, and Federico Ricci-Tersenghi · 2016
Later among the works it cites.
Mutual information in rank-one matrix estimation
Florent Krzakala, Jiaming Xu, and Lenka Zdeborová · 2016
Later among the works it cites.
Fundamental limits of symmetric low-rank matrix estimation
Marc Lelarge and Léo Miolane · 2016
Later among the works it cites.
Non-negative principal component analysis: Message passing algorithms and sharp asymptotics
Andrea Montanari and Emile Richard · 2016
Later among the works it cites.
Polynomial-time tensor decompositions with sum-of-squares
Tengyu Ma, Jonathan Shi, and David Steurer · 2016
Later among the works it cites.
Statistical limits of spiked tensor models
Amelia Perry, Alexander S Wein, and Afonso S Bandeira · 2016
Later among the works it cites.
Message-passing algorithms for synchronization problems over compact groups
Amelia Perry, Alexander S Wein, Afonso S Bandeira, and Ankur Moitra · 2016
Later among the works it cites.
Optimality and sub-optimality of PCA for spiked random matrices and synchronization
Amelia Perry, Alexander S Wein, Afonso S Bandeira, and Ankur Moitra · 2016
Later among the works it cites.
Statistical physics of inference: Thresholds and algorithms
Lenka Zdeborová and Florent Krzakala · 2016
Later among the works it cites.
Community detection and stochastic block models: recent developments
Emmanuel Abbe · 2017
Later among the works it cites.
No spurious local minima in nonconvex low rank problems: A unified geometric analysis
Rong Ge, Chi Jin, and Yi Zheng · 2017
Later among the works it cites.
On the optimization landscape of tensor decompositions
R. Ge and T. Ma · 2017
Later among the works it cites.
Bayesian estimation from few samples: community detection and related problems
Samuel B Hopkins and David Steurer · 2017
Later among the works it cites.
Community detection in hypergraphs, spiked tensor models, and sum-of-squares
C. Kim, A. S. Bandeira, and M. X. Goemans · 2017
Later among the works it cites.
Statistical and computational phase transitions in spiked tensor estimation
T. Lesieur, L. Miolane, M. Lelarge, F. Krzakala, and L. Zdeborová · 2017
Later among the works it cites.
The computer science and physics of community detection: Landscapes, phase transitions, and hardness
Cristopher Moore · 2017
Later among the works it cites.
Exact tensor completion with sum-of-squares
Aaron Potechin and David Steurer · 2017
Later among the works it cites.
Neural networks with finite intrinsic dimension have no spurious valleys
J. Bruna L. Venturi, A. S. Bandeira · 2018
Closest in time.