Fetching the paper…
Reading the bibliography…
These notes survey and explore an emerging method, which we call the low-degree method, for predicting and understanding statistical-versus-computational tradeoffs in high-dimensional inference problems.
IX. on the problem of the most efficient tests of statistical hypotheses
Jerzy Neyman and Egon Sharpe Pearson · 1933
Earlier work this paper cites.
Orthogonal polynomials
Gabor Szegö · 1939
Earlier work this paper cites.
Locally asymptotically normal families of distributions
Lucien Le Cam · 1960
Earlier work this paper cites.
Factoring polynomials with rational coefficients
Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász · 1982
Earlier work this paper cites.
Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications
Marc Mézard, Giorgio Parisi, and Miguel Virasoro · 1987
Earlier work this paper cites.
Large cliques elude the Metropolis process
Mark Jerrum · 1992
Earlier work this paper cites.
Almost all cubic graphs are hamiltonian
Robert W Robinson and Nicholas C Wormald · 1992
Earlier work this paper cites.
Almost all regular graphs are hamiltonian
Robert W Robinson and Nicholas C Wormald · 1994
Earlier work this paper cites.
Color-coding
Noga Alon, Raphael Yuster, and Uri Zwick · 1995
Earlier work this paper cites.
Expected complexity of graph partitioning problems
Luděk Kučera · 1995
Earlier work this paper cites.
Gaussian hilbert spaces
Svante Janson · 1997
Earlier work this paper cites.
Finding a large hidden clique in a random graph
Noga Alon, Michael Krivelevich, and Benny Sudakov · 1998
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
Michael Kearns · 1998
Earlier work this paper cites.
Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization
Pablo A Parrilo · 2000
Earlier work this paper cites.
Heuristics for semirandom graph problems
Uriel Feige and Joe Kilian · 2001
Earlier work this paper cites.
Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
Dima Grigoriev · 2001
Earlier work this paper cites.
Global optimization with polynomials and the problem of moments
Jean B Lasserre · 2001
Earlier work this paper cites.
On counting independent sets in sparse graphs
Martin Dyer, Alan Frieze, and Mark Jerrum · 2002
Earlier work this paper cites.
Noise-tolerant learning, the parity problem, and the statistical query model
Avrim Blum, Adam Kalai, and Hal Wasserman · 2003
Earlier work this paper cites.
Sparse principal components analysis
Iain M. Johnstone and Arthur Yu Lu · 2004
Earlier work this paper cites.
Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
Jinho Baik, Gérard Ben Arous, and Sandrine Péché · 2005
Earlier work this paper cites.
Testing statistical hypotheses
Erich L Lehmann and Joseph P Romano · 2006
Earlier work this paper cites.
The largest eigenvalue of rank one deformation of large Wigner matrices
Delphine Féral and Sandrine Péché · 2007
Earlier work this paper cites.
Gibbs states and the set of solutions of random constraint satisfaction problems
Florent Krzakała, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová · 2007
Earlier work this paper cites.
Unconditional lower bounds for learning intersections of halfspaces
Adam R Klivans and Alexander A Sherstov · 2007
Earlier work this paper cites.
Algorithmic barriers from phase transitions
Dimitris Achlioptas and Amin Coja-Oghlan · 2008
Earlier work this paper cites.
High-dimensional analysis of semidefinite relaxations for sparse principal components
Arash A Amini and Martin J Wainwright · 2008
Earlier work this paper cites.
Linear level Lasserre lower bounds for certain k-CSPs
Grant Schoenebeck · 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.
On consistency and sparsity for principal components analysis in high dimensions
Iain M Johnstone and Arthur Yu Lu · 2009
Earlier work this paper cites.
Information, physics, and computation
Marc Mezard and Andrea Montanari · 2009
Earlier work this paper cites.
Real analysis: measure theory, integration, and Hilbert spaces
Elias M Stein and Rami Shakarchi · 2009
Earlier work this paper cites.
The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices
Florent Benaych-Georges and Raj Rao Nadakuditi · 2011
Earlier work this paper cites.
Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová · 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.
Asymptotic methods in statistical decision theory
Lucien Le Cam · 2012
Earlier work this paper cites.
Random matrices and complexity of spin glasses
Antonio Auffinger, Gérard Ben Arous, and Jiří Černỳ · 2013
Cited alongside, same era.
Computational lower bounds for sparse PCA
Quentin Berthet and Philippe Rigollet · 2013
Cited alongside, same era.
Spectral redemption in clustering sparse networks
Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang · 2013
Cited alongside, same era.
Sparse PCA via covariance thresholding
Yash Deshpande and Andrea Montanari · 2014
Cited alongside, same era.
Limits of local algorithms over sparse random graphs
David Gamarnik and Madhu Sudan · 2014
Cited alongside, same era.
Community detection thresholds and the weak Ramanujan property
Laurent Massoulié · 2014
Cited alongside, same era.
Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures
Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart · 2017
Later among the works it cites.
Finite size corrections and likelihood ratio fluctuations in the spiked Wigner model
Ahmed El Alaoui, Florent Krzakala, and Michael I Jordan · 2017
Later among the works it cites.
Statistical algorithms and a lower bound for detecting planted cliques
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao · 2017
Later among the works it cites.
Sparse high-dimensional linear regression. algorithmic barriers and a local search algorithm
David Gamarnik and Ilias Zadik · 2017
Later among the works it cites.
The power of sum-of-squares for detecting hidden structures
Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer · 2017
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Analysis of boolean functions
Ryan O’Donnell · 2014
Cited alongside, same era.
A statistical model for tensor PCA
Emile Richard and Andrea Montanari · 2014
Cited alongside, same era.
Spectral clustering of graphs with the Bethe Hessian
Alaa Saade, Florent Krzakala, and Lenka Zdeborová · 2014
Cited alongside, same era.
Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs
Charles Bordenave, Marc Lelarge, and Laurent Massoulié · 2015
Cited alongside, same era.
Asymptotic mutual information for the two-groups stochastic block model
Yash Deshpande, Emmanuel Abbe, and Andrea Montanari · 2015
Cited alongside, same era.
Finding hidden cliques of size sqrt(n/e) in nearly linear time
Yash Deshpande and Andrea Montanari · 2015
Cited alongside, same era.
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.
Sum of squares lower bounds for refuting any CSP
Pravesh K Kothari, Ryuhei Mori, Ryan O’Donnell, and David Witmer · 2017
Later among the works it cites.
Statistical and computational phase transitions in spiked tensor estimation
Thibault Lesieur, Léo Miolane, Marc Lelarge, Florent Krzakala, and Lenka Zdeborová · 2017
Later among the works it cites.
Strongly refuting random CSPs below the spectral threshold
Prasad Raghavendra, Satish Rao, and Tselil Schramm · 2017
Later among the works it cites.
Reducibility and computational lower bounds for problems with planted sparse structure
Matthew Brennan, Guy Bresler, and Wasim Huleihel · 2018
Later among the works it cites.
Algorithmic thresholds for tensor PCA
Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath · 2018
Later among the works it cites.
Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
Jess Banks, Cristopher Moore, Roman Vershynin, Nicolas Verzelen, and Jiaming Xu · 2018
Later among the works it cites.
Notes on computational-to-statistical gaps: predictions using statistical physics
Afonso S Bandeira, Amelia Perry, and Alexander S Wein · 2018
Later among the works it cites.
Estimation in the spiked Wigner model: A short proof of the replica formula
Ahmed El Alaoui and Florent Krzakala · 2018
Later among the works it cites.
Fundamental limits of detection in the spiked Wigner model
Ahmed El Alaoui, Florent Krzakala, and Michael I Jordan · 2018
Later among the works it cites.
On the complexity of random satisfiability problems with planted solutions
Vitaly Feldman, Will Perkins, and Santosh Vempala · 2018
Later among the works it cites.
Statistical Inference and the Sum of Squares Method
Samuel Hopkins · 2018
Later among the works it cites.
Statistical thresholds for tensor pca
Aukosh Jagannath, Patrick Lopatto, and Leo Miolane · 2018
Later among the works it cites.
Phase transitions in spiked matrix estimation: information-theoretic analysis
Léo Miolane · 2018
Later among the works it cites.
A proof of the block model threshold conjecture
Elchanan Mossel, Joe Neeman, and Allan Sly · 2018
Later among the works it cites.
Planting trees in graphs, and finding them back
Laurent Massoulié, Ludovic Stephan, and Don Towsley · 2018
Later among the works it cites.
Optimality and sub-optimality of PCA I: Spiked random matrix models
Amelia Perry, Alexander S Wein, Afonso S Bandeira, and Ankur Moitra · 2018
Later among the works it cites.
High-dimensional statistics
Philippe Rigollet and Jan-Christian Hütter · 2018
Later among the works it cites.
High-dimensional estimation via sum-of-squares proofs
Prasad Raghavendra, Tselil Schramm, and David Steurer · 2018
Later among the works it cites.
High dimensional linear regression using lattice basis reduction
Ilias Zadik and David Gamarnik · 2018
Later among the works it cites.
Optimal average-case reductions to sparse PCA: From weak assumptions to strong hardness
Matthew Brennan and Guy Bresler · 2019
Closest in time.
A nearly tight sum-of-squares lower bound for the planted clique problem
Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K Kothari, Ankur Moitra, and Aaron Potechin · 2019
Closest in time.
Computational hardness of certifying bounds on constrained PCA problems
Afonso S Bandeira, Dmitriy Kunisky, and Alexander S Wein · 2019
Closest in time.
Suboptimality of local algorithms for a class of max-cut problems
Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko, and Mustazee Rahman · 2019
Closest in time.
Robust estimators in high-dimensions without the computational intractability
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart · 2019
Closest in time.
Subexponential-time algorithms for sparse PCA
Yunzi Ding, Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira · 2019
Closest in time.
The landscape of the planted clique problem: Dense subgraphs and the overlap gap property
David Gamarnik and Ilias Zadik · 2019
Closest in time.
Fundamental limits of symmetric low-rank matrix estimation
Marc Lelarge and Léo Miolane · 2019
Closest in time.
Passed & spurious: Descent algorithms and local minima in spiked matrix-tensor models
Stefano Sarao Mannelli, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborova · 2019
Closest in time.
The Kikuchi hierarchy and tensor PCA
Alexander S Wein, Ahmed El Alaoui, and Cristopher Moore · 2019
Closest in time.