Fetching the paper…
Reading the bibliography…
Over the past few years, insights from computer science, statistical physics, and information theory have revealed phase transitions in a wide array of high-dimensional statistical problems at two distinct thresholds: One is the information-theoretical (IT) threshold below which the observation is too noisy so that inference of the ground truth structure is impossible regardless of the computational cost; the other is the computational threshold above which inference can be performed efficiently, i.e., in time that is polynomial in the input size.
On the convergence of sequences of moment generating functions
W. Kozakiewicz · 1947
Earlier work this paper cites.
Information-type measures of difference of probability distributions and indirect observations
I. Csiszár · 1967
Earlier work this paper cites.
An Introduction to Probability Theory and Its Applications
W. Feller · 1970
Earlier work this paper cites.
Statistical Estimation: Asymptotic Theory
I. A. Ibragimov and R. Z. Khas’minskĭ · 1981
Earlier work this paper cites.
Approximation dans les espaces métriques et théorie de l’estimation
Lucien Birgé · 1983
Earlier work this paper cites.
Stochastic blockmodels: First steps
P. W. Holland, K. B. Laskey, and S. Leinhardt · 1983
Earlier work this paper cites.
Asymptotic methods in statistical decision theory
Lucien Le Cam · 1986
Earlier work this paper cites.
Information inequality bounds on the minimax risk (with an application to nonparametric regression)
L. D. Brown and M. G. Low · 1991
Earlier work this paper cites.
Large cliques elude the Metropolis process
Mark Jerrum · 1992
Earlier work this paper cites.
A generalized encryption scheme based on random graphs
L. Kučera · 1992
Earlier work this paper cites.
Almost independence and secrecy capacity
Imre Csiszár · 1996
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.
Theory of Point Estimation
E. L. Lehmann and G. Casella · 1998
Earlier work this paper cites.
Information-theoretic determination of minimax rates of convergence
Y. Yang and A. R. Barron · 1999
Earlier work this paper cites.
Finding and certifying a large hidden clique in a semirandom graph
Uriel Feige and Robert Krauthgamer · 2000
Earlier work this paper cites.
Hiding cliques for cryptographic security
A. Juels and M. Peinado · 2000
Earlier work this paper cites.
Asymptotic statistics
Aad W. Van der Vaart · 2000
Earlier work this paper cites.
Spectral partitioning of random graphs
F. McSherry · 2001
Earlier work this paper cites.
Nonparametric goodness-of-fit testing under Gaussian models
Y. I. Ingster and I. A. Suslina · 2003
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.
Mutual information and minimum mean-square error in gaussian channels
Dongning Guo, Shlomo Shamai, and Sergio Verdú · 2005
Earlier work this paper cites.
The largest eigenvalue of small rank perturbations of hermitian random matrices
Sandrine Péché · 2006
Earlier work this paper cites.
Testing k k -wise and almost k k -wise independence
N. Alon, A. Andoni, T. Kaufman, K. Matulef, R. Rubinfeld, and N. Xie · 2007
Earlier work this paper cites.
Asymptotics of sample eigenstruture for a large dimensional spiked covariance model
D. Paul · 2007
Earlier work this paper cites.
Finding large average submatrices in high dimensional data
A. A. Shabalin, V. J. Weigman, C. M. Perou, and A. B Nobel · 2009
Earlier work this paper cites.
Introduction to Nonparametric Estimation
A. B. Tsybakov · 2009
Earlier work this paper cites.
On metric divergences of probability measures
I. Vajda · 2009
Earlier work this paper cites.
Public-key cryptography from different assumptions
B. Applebaum, B. Barak, and A. Wigderson · 2010
Earlier work this paper cites.
Finding hidden cliques in linear time
Uriel Feige and Dorit Ron · 2010
Earlier work this paper cites.
Average-case complexity of detecting cliques
B. Rossman · 2010
Earlier work this paper cites.
Inapproximabilty of densest κ \kappa -subgraph from average case hardness
N. Alon, S. Arora, R. Manokaran, D. Moshkovitz, and O. Weinstein · 2011
Earlier work this paper cites.
Nuclear norm minimization for the planted clique and biclique problems
Brendan PW Ames and Stephen A Vavasis · 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.
How hard is it to approximate the best nash equilibrium?
E. Hazan and R. Krauthgamer · 2011
Earlier work this paper cites.
Minimax localization of structural information in large noisy matrices
M. Kolar, S. Balakrishnan, A. Rinaldo, and A. Singh · 2011
Cited alongside, same era.
On the certification of the restricted isometry property
Pascal Koiran and Anastasios Zouzias · 2011
Cited alongside, same era.
Large Networks and Graph Limits
László Lovász · 2012
Cited alongside, same era.
Robust convex relaxation for the planted clique and densest k-subgraph problems
B.P.W Ames · 2013
Cited alongside, same era.
Detection of a sparse submatrix of a high-dimensional noisy matrix
Cristina Butucea and Yuri I. Ingster · 2013
Cited alongside, same era.
Complexity theoretic lower bounds for sparse principal component detection
Q. Berthet and P. Rigollet · 2013
Sum-of-squares lower bounds for planted clique
R. Meka, A. Potechin, and A. Wigderson · 2015
Later among the works it cites.
On the limitation of spectral methods: From the Gaussian hidden clique problem to rank one perturbations of Gaussian tensors
A. Montanari, D. Reichman, and O. Zeitouni · 2015
Later among the works it cites.
Computational barriers in minimax submatrix detection
Z. Ma and Y. Wu · 2015
Later among the works it cites.
Lecture Notes on Information Theory
Yury Polyanskiy and Yihong Wu · 2015
Later among the works it cites.
Tight lower bounds for planted clique in the degree-4 SOS program
P. Raghavendra and T. Schramm · 2015
Later among the works it cites.
Community detection in sparse random networks
Nicolas Verzelen, Ery Arias-Castro, et al · 2015
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Statistical algorithms and a lower bound for detecting planted cliques
V. Feldman, E. Grigorescu, L. Reyzin, S. Vempala, and Y. Xiao · 2013
Cited alongside, same era.
Most tensor problems are NP-hard
Christopher J. Hillar and Lek-Heng Lim · 2013
Cited alongside, same era.
Spectral redemption in clustering sparse networks
F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborová, and P. Zhang · 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.
Community detection in dense random networks
Ery Arias-Castro and Nicolas Verzelen · 2014
Cited alongside, same era.
Y. Chen and J. Xu · 2014
Cited alongside, same era.
Later among the works it cites.
Exact recovery in the stochastic block model
E. Abbe, A. S. Bandeira, and G. Hall · 2016
Later among the works it cites.
Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
Jean Barbier, Mohamad Dia, Nicolas Macris, Florent Krzakala, Thibault Lesieur, and Lenka Zdeborová · 2016
Later among the works it cites.
A nearly tight sum-of-squares lower bound for the planted clique problem
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, and Aaron Potechin · 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.
Semidefinite programs for exact recovery of a hidden community
Bruce Hajek, Yihong Wu, and Jiaming Xu · 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.
Phase transitions and optimal algorithms in high-dimensional gaussian mixture clustering
Thibault Lesieur, Caterina De Bacco, Jess Banks, Florent Krzakala, Cris Moore, and Lenka Zdeborová · 2016
Later among the works it cites.
Dissipation of information in channels with input constraints
Yury Polyanskiy and Yihong Wu · 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.
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 and computational trade-offs in estimation of sparse principal components
Tengyao Wang, Quentin Berthet, and Richard J Samworth · 2016
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.
Computational and statistical boundaries for submatrix localization in a large noisy matrix
T Tony Cai, Tengyuan Liang, and Alexander Rakhlin · 2017
Later among the works it cites.
Sparse CCA: Adaptive estimation and computational barriers
Chao Gao, Zongming Ma, and Harrison H Zhou · 2017
Later among the works it cites.
Information limits for recovering a hidden community
B. Hajek, Y. Wu, and J. Xu · 2017
Later among the works it cites.
Optimal graphon estimation in cut distance
Olga Klopp and Nicolas Verzelen · 2017
Later among the works it cites.
Fundamental limits of symmetric low-rank matrix estimation
Marc Lelarge and Léo Miolane · 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.
Lecture notes on information-theoretic methods for high-dimensional statistics
Yihong Wu · 2017
Later among the works it cites.
Tensor SVD: Statistical and computational limits
Anru Zhang and Dong Xia · 2017
Later among the works it cites.
An information-percolation bound for spin synchronization on general graphs
Emmanuel Abbe and Enric Boix · 2018
Closest in time.
Estimation in the spiked Wigner model: A short proof of the replica formula
Ahmed El Alaoui and Florent Krzakala · 2018
Closest in time.
Reducibility and computational lower bounds for problems with planted sparse structure
Matthew Brennan, Guy Bresler, and Wasim Huleihel · 2018
Closest in time.
Information-theoretic bounds and phase transitions in clustering, sparse pca, and submatrix localization
J. Banks, C. Moore, R. Vershynin, N. Verzelen, and J. Xu · 2018
Closest in time.
Submatrix localization via message passing
Bruce Hajek, Yihong Wu, and Jiaming Xu · 2018
Closest in time.
Application of information-percolation method to reconstruction problems on graphs
Yury Polyanskiy and Yihong Wu · 2018
Closest in time.
Rates of convergence of spectral methods for graphon estimation
Jiaming Xu · 2018
Closest in time.