Fetching the paper…
Reading the bibliography…
One fundamental goal of high-dimensional statistics is to detect or recover planted structure (such as a low-rank matrix) hidden in noisy data.
Orthogonal polynomials
Gabor Szegö · 1939
Earlier work this paper cites.
On the degree of polynomials that approximate symmetric boolean functions (preliminary version)
Ramamohan Paturi · 1992
Earlier work this paper cites.
Random-self-reducibility of complete sets
Joan Feigenbaum and Lance Fortnow · 1993
Earlier work this paper cites.
On the degree of boolean functions as real polynomials
Noam Nisan and Mario Szegedy · 1994
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
Michael Kearns · 1998
Earlier work this paper cites.
Higher criticism for detecting sparse heterogeneous mixtures
David Donoho and Jiashun Jin · 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.
On basing one-way functions on NP-hardness
Adi Akavia, Oded Goldreich, Shafi Goldwasser, and Dana Moshkovitz · 2006
Earlier work this paper cites.
Eigenvalues of large sample covariance matrices of spiked population models
Jinho Baik and Jack W Silverstein · 2006
Earlier work this paper cites.
On worst-case to average-case reductions for NP problems
Andrej Bogdanov and Luca Trevisan · 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.
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.
The largest eigenvalues of finite rank deformation of large wigner matrices: convergence and nonuniversality of the fluctuations
Mireille Capitaine, Catherine Donati-Martin, and Delphine Féral · 2009
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.
Finding large average submatrices in high dimensional data
Andrey A Shabalin, Victor J Weigman, Charles M Perou, and Andrew B Nobel · 2009
Earlier work this paper cites.
Detecting high log-densities: an O ( n 1 / 4 ) O(n^{1/4}) approximation for densest k-subgraph
Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan · 2010
Earlier work this paper cites.
Detection of an anomalous cluster in a network
Ery Arias-Castro, Emmanuel J Candes, and Arnaud Durand · 2011
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.
Statistical and computational tradeoffs in biclustering
Sivaraman Balakrishnan, Mladen Kolar, Alessandro Rinaldo, Aarti Singh, and Larry Wasserman · 2011
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.
Minimax localization of structural information in large noisy matrices
Mladen Kolar, Sivaraman Balakrishnan, Alessandro Rinaldo, and Aarti Singh · 2011
Earlier work this paper cites.
Iterative estimation of constrained rank-one matrices in noise
Sundeep Rangan and Alyson K Fletcher · 2012
Earlier work this paper cites.
Robust convex relaxation for the planted clique and densest k-subgraph problems
Brendan PW Ames · 2013
Earlier work this paper cites.
Community detection in random networks
Ery Arias-Castro and Nicolas Verzelen · 2013
Earlier work this paper cites.
Detection of a sparse submatrix of a high-dimensional noisy matrix
Cristina Butucea and Yuri I Ingster · 2013
Earlier work this paper cites.
Complexity theoretic lower bounds for sparse principal component detection
Quentin Berthet and Philippe Rigollet · 2013
Earlier work this paper cites.
State evolution for general approximate message passing algorithms, with applications to spatial coupling
Adel Javanmard and Andrea Montanari · 2013
Earlier work this paper cites.
Formulas and theorems for the special functions of mathematical physics
Wilhelm Magnus, Fritz Oberhettinger, and Raj Pal Soni · 2013
Earlier work this paper cites.
An iterative construction of solutions of the TAP equations for the Sherrington–Kirkpatrick model
Erwin Bolthausen · 2014
Earlier work this paper cites.
Information-theoretically optimal sparse PCA
Yash Deshpande and Andrea Montanari · 2014
Earlier work this paper cites.
Limits of local algorithms over sparse random graphs
David Gamarnik and Madhu Sudan · 2014
Earlier work this paper cites.
Three lectures on free probability
Jonathan Novak · 2014
Earlier work this paper cites.
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.
Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix
Cristina Butucea, Yuri I Ingster, and Irina A Suslina · 2015
Cited alongside, same era.
Incoherence-optimal matrix completion
Yudong Chen · 2015
Cited alongside, same era.
Finding hidden cliques of size N / e \sqrt{N/e} in nearly linear time
Yash Deshpande and Andrea Montanari · 2015
Cited alongside, same era.
Tensor principal component analysis via sum-of-squares proofs
Samuel B Hopkins, Jonathan Shi, and David Steurer · 2015
Cited alongside, same era.
High-dimensional estimation via sum-of-squares proofs
Prasad Raghavendra, Tselil Schramm, and David Steurer · 2018
Later among the works it cites.
Tensor SVD: Statistical and computational limits
Anru Zhang and Dong Xia · 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
Later among the works it cites.
(Nearly) efficient algorithms for the graph matching problem on correlated random graphs
Boaz Barak, Chi-Ning Chou, Zhixian Lei, Tselil Schramm, and Yueqi Sheng · 2019
Later among the works it cites.
Giulio Biroli, Chiara Cammarota, and Federico Ricci-Tersenghi · 2019
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Computational lower bounds for community detection on random graphs
Bruce Hajek, Yihong Wu, and Jiaming Xu · 2015
Cited alongside, same era.
MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
Thibault Lesieur, Florent Krzakala, and Lenka Zdeborová · 2015
Cited alongside, same era.
Phase transitions in sparse PCA
Thibault Lesieur, Florent Krzakala, and Lenka Zdeborová · 2015
Cited alongside, same era.
Computational barriers in minimax submatrix detection
Zongming Ma and Yihong Wu · 2015
Cited alongside, same era.
Community detection in sparse random networks
Nicolas Verzelen and Ery Arias-Castro · 2015
Cited alongside, same era.
Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
Yudong Chen and Jiaming Xu · 2016
Cited alongside, same era.
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
Later among the works it cites.
The lovász theta function for random regular graphs and community detection in the hard regime
Jess Banks, Robert Kleinberg, and Cristopher Moore · 2019
Later among the works it cites.
Local statistics, semidefinite programming, and community detection
Jess Banks, Sidhanth Mohanty, and Prasad Raghavendra · 2019
Later among the works it cites.
Suboptimality of local algorithms for a class of max-cut problems
Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko, and Mustazee Rahman · 2019
Later among the works it cites.
Subexponential-time algorithms for sparse PCA
Yunzi Ding, Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira · 2019
Later among the works it cites.
The overlap gap property and approximate message passing algorithms for p-spin models
David Gamarnik and Aukosh Jagannath · 2019
Later among the works it cites.
The overlap gap property in principal submatrix recovery
David Gamarnik, Aukosh Jagannath, and Subhabrata Sen · 2019
Later among the works it cites.
The landscape of the planted clique problem: Dense subgraphs and the overlap gap property
David Gamarnik and Ilias Zadik · 2019
Later among the works it cites.
A robust spectral algorithm for overcomplete tensor decomposition
Samuel B Hopkins, Tselil Schramm, and Jonathan Shi · 2019
Later among the works it cites.
Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira · 2019
Later among the works it cites.
Optimization of the Sherrington-Kirkpatrick hamiltonian
Andrea Montanari · 2019
Later among the works it cites.
Planting trees in graphs, and finding them back
Laurent Massoulié, Ludovic Stephan, and Don Towsley · 2019
Later among the works it cites.
The Kikuchi hierarchy and tensor PCA
Alexander S Wein, Ahmed El Alaoui, and Cristopher Moore · 2019
Later among the works it cites.
Reducibility and statistical-computational gaps from secret leakage
Matthew Brennan and Guy Bresler · 2020
Closest in time.
Computational hardness of certifying bounds on constrained PCA problems
Afonso S Bandeira, Dmitriy Kunisky, and Alexander S Wein · 2020
Closest in time.
All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation
Jean Barbier, Nicolas Macris, and Cynthia Rush · 2020
Closest in time.
Free energy wells and overlap gap property in sparse PCA
Gérard Ben Arous, Alexander S Wein, and Ilias Zadik · 2020
Closest in time.
Sum-of-squares lower bounds for Sherrington-Kirkpatrick via planted affine planes
Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, and Goutham Rajendran · 2020
Closest in time.
Low-degree hardness of random optimization problems
David Gamarnik, Aukosh Jagannath, and Alexander S Wein · 2020
Closest in time.
A greedy anytime algorithm for sparse PCA
Guy Holtzman, Adam Soffer, and Dan Vilenchik · 2020
Closest in time.
Counterexamples to the low-degree conjecture
Justin Holmgren and Alexander S Wein · 2020
Closest in time.
Computationally efficient sparse clustering
Matthias Löffler, Alexander S Wein, and Afonso S Bandeira · 2020
Closest in time.
Lifting sum-of-squares lower bounds: degree-2 to degree-4
Sidhanth Mohanty, Prasad Raghavendra, and Jeff Xu · 2020
Closest in time.
Optimal low-degree hardness of maximum independent set
Alexander S Wein · 2020
Closest in time.
Statistical query algorithms and low-degree tests are almost equivalent
Matthew Brennan, Guy Bresler, Samuel B. Hopkins, Jerry Li, and Tselil Schramm · 2021
Closest in time.
Spectral planting and the hardness of refuting cuts, colorability, and communities in random graphs
Afonso S Bandeira, Jess Banks, Dmitriy Kunisky, Christopher Moore, and Alex Wein · 2021
Closest in time.
The algorithmic phase transition of random k k -SAT for low degree polynomials
Guy Bresler and Brice Huang · 2021
Closest in time.
Statistical query lower bounds for tensor PCA
Rishabh Dudeja and Daniel Hsu · 2021
Closest in time.