Fetching the paper…
Reading the bibliography…
The prototypical high-dimensional statistics problem entails finding a structured signal in noise.
Average case complete problems
Leonid A Levin · 1986
Earlier work this paper cites.
A dozen de finetti-style results in search of a theory
Persi Diaconis and David Freedman · 1987
Earlier work this paper cites.
Large cliques elude the metropolis process
Mark Jerrum · 1992
Earlier work this paper cites.
Some probabilistic aspects of set partitions
Jim Pitman · 1997
Earlier work this paper cites.
Assouad, fano, and le cam
Bin Yu · 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.
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
Ari Juels and Marcus Peinado · 2000
Earlier work this paper cites.
Spectral partitioning of random graphs
Frank McSherry · 2001
Earlier work this paper cites.
Relations between average case complexity and approximation complexity
Uriel Feige · 2002
Earlier work this paper cites.
Finding large independent sets in polynomial expected time
Amin Coja-Oghlan · 2003
Earlier work this paper cites.
The probable value of the lovász–schrijver relaxations for maximum independent set
Uriel Feige and Robert Krauthgamer · 2003
Earlier work this paper cites.
Sparse principal components analysis
Iain M Johnstone and Arthur Yu Lu · 2004
Earlier work this paper cites.
Finding a maximum independent set in a sparse random graph
Uriel Feige and Eran Ofek · 2005
Earlier work this paper cites.
Spectral norm of random matrices
Van H Vu · 2005
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.
Average-case complexity
Andrej Bogdanov, Luca Trevisan, et al · 2006
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-wise and almost k-wise independence
Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, and Ning Xie · 2007
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.
Concentration inequalities and model selection
Pascal Massart · 2007
Earlier work this paper cites.
Asymptotics of sample eigenstructure for a large dimensional spiked covariance model
Debashis Paul · 2007
Earlier work this paper cites.
Computational complexity: a modern approach
Sanjeev Arora and Boaz Barak · 2009
Earlier work this paper cites.
High-dimensional analysis of semidefinite relaxations for sparse principal components
Arash A Amini and Martin J Wainwright · 2009
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, Delphine Féral, et al · 2009
Earlier work this paper cites.
Small clique detection and approximate nash equilibria
Lorenz Minder and Dan Vilenchik · 2009
Earlier work this paper cites.
Finding large average submatrices in high dimensional data
Andrey A Shabalin, Victor J Weigman, Charles M Perou, Andrew B Nobel, et al · 2009
Earlier work this paper cites.
Public-key cryptography from different assumptions
Benny Applebaum, Boaz Barak, and Avi Wigderson · 2010
Earlier work this paper cites.
Detecting high log-densities: an o ( n 1 / 4 ) o(n^{1/4}) approximation for densest k k -subgraph
Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan · 2010
Earlier work this paper cites.
Finding hidden cliques in linear time
Uriel Feige and Dorit Ron · 2010
Earlier work this paper cites.
Introduction to the non-asymptotic analysis of random matrices
Roman Vershynin · 2010
Earlier work this paper cites.
Inapproximability of densest κ \kappa -subgraph from average case hardness
Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, and Omri Weinstein · 2011
Earlier work this paper cites.
Computational complexity and information asymmetry in financial products
Sanjeev Arora, Boaz Barak, Markus Brunnermeier, and Rong Ge · 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.
Statistical and computational tradeoffs in biclustering
Sivaraman Balakrishnan, Mladen Kolar, Alessandro Rinaldo, Aarti Singh, and Larry Wasserman · 2011
Earlier work this paper cites.
How hard is it to approximate the best nash equilibrium?
Elad Hazan and Robert Krauthgamer · 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.
Everywhere-sparse spanners via dense subgraphs
Eden Chlamtac, Michael Dinitz, and Robert Krauthgamer · 2012
Earlier work this paper cites.
Approximating the minmax value of 3-player games within a constant is as hard as detecting planted cliques
Kord Eickmeyer, Kristoffer Arnsfelt Hansen, and Elad Verbin · 2012
Earlier work this paper cites.
Statistical algorithms and a lower bound for planted clique
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, and Ying Xiao · 2012
Cited alongside, same era.
Stochastic block models and reconstruction
Elchanan Mossel, Joe Neeman, and Allan Sly · 2012
Cited alongside, same era.
Minimax rates of estimation for sparse pca in high dimensions
Vincent Q Vu and Jing Lei · 2012
Cited alongside, same era.
Inapproximability of np-complete variants of nash equilibrium
Per Austrin, Mark Braverman, and Eden Chlamtác · 2013
Cited alongside, same era.
Finding endogenously formed communities
Maria-Florina Balcan, Christian Borgs, Mark Braverman, Jennifer Chayes, and Shang-Hua Teng · 2013
Cited alongside, same era.
Computational barriers in minimax submatrix detection
Zongming Ma and Yihong Wu · 2015
Later among the works it cites.
Tight lower bounds for planted clique in the degree-4 sos program
Prasad Raghavendra and Tselil Schramm · 2015
Later among the works it cites.
Community detection in sparse random networks
Nicolas Verzelen, Ery Arias-Castro, et al · 2015
Later among the works it cites.
Exact recovery in the stochastic block model
Emmanuel Abbe, Afonso S Bandeira, and Georgina Hall · 2016
Later among the works it cites.
Hardness results for signaling in bayesian zero-sum and network routing games
Umang Bhaskar, Yu Cheng, Young Kun Ko, and Chaitanya Swamy · 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 Kelner, Pravesh Kothari, Ankur Moitra, and Aaron Potechin · 2016
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cristina Butucea and Yuri I Ingster · 2013
Cited alongside, same era.
Minimax bounds for sparse pca with noisy high-dimensional data
Aharon Birnbaum, Iain M Johnstone, Boaz Nadler, and Debashis Paul · 2013
Cited alongside, same era.
Complexity theoretic lower bounds for sparse principal component detection
Quentin Berthet and Philippe Rigollet · 2013
Cited alongside, same era.
Optimal detection of sparse principal components in high dimension
Quentin Berthet and Philippe Rigollet · 2013
Cited alongside, same era.
Computational and statistical tradeoffs via convex relaxation
Venkat Chandrasekaran and Michael I Jordan · 2013
Cited alongside, same era.
Sparse pca: Optimal rates and adaptive estimation
T Tony Cai, Zongming Ma, Yihong Wu, et al · 2013
Cited alongside, same era.
Statistical algorithms and a lower bound for detecting planted cliques
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, and Ying Xiao · 2013
Cited alongside, same era.
Later among the works it cites.
On the approximability of sparse pca
Siu On Chan, Dimitris Papailliopoulos, and Aviad Rubinstein · 2016
Later among the works it cites.
Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
Yudong Chen and Jiaming Xu · 2016
Later among the works it cites.
Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart · 2016
Later among the works it cites.
Complexity theoretic limitations on learning dnf’s
Amit Daniely and Shai Shalev-Shwartz · 2016
Later among the works it cites.
On the integrality gap of degree-4 sum of squares for planted clique
Samuel B Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, and Tselil Schramm · 2016
Later among the works it cites.
Achieving exact cluster recovery threshold via semidefinite programming
Bruce Hajek, Yihong Wu, and Jiaming Xu · 2016
Later among the works it cites.
Information limits for recovering a hidden community
Bruce Hajek, Yihong Wu, and Jiaming Xu · 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.
Feeling the bern: Adaptive estimators for bernoulli probabilities of pairwise comparisons
Nihar B Shah, Sivaraman Balakrishnan, and Martin J Wainwright · 2016
Later among the works it cites.
Average-case hardness of rip certification
Tengyao Wang, Quentin Berthet, and Yaniv Plan · 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.
Community detection and stochastic block models: recent developments
Emmanuel Abbe · 2017
Later among the works it cites.
The Complexity of Public-Key Cryptography
Boaz Barak · 2017
Later among the works it cites.
Computationally efficient robust sparse estimation in high dimensions
Sivaraman Balakrishnan, Simon S Du, Jerry Li, and Aarti Singh · 2017
Later among the works it cites.
Sum-of-squares certificates for maxima of random tensors on the sphere
Vijay Bhattiprolu, Venkatesan Guruswami, and Euiwoong Lee · 2017
Later among the works it cites.
Minimizing the union: Tight approximations for small set bipartite vertex expansion
Eden Chlamtáč, Michael Dinitz, and Yury Makarychev · 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.
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
Later among the works it cites.
On the average-case complexity of mcsp and its variants
Shuichi Hirahara and Rahul Santhanam · 2017
Later among the works it cites.
Efficient 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.
Robust sparse estimation tasks in high dimensions
Jerry Li · 2017
Later among the works it cites.
Local algorithms for independent sets are half-optimal
Mustazee Rahman, Balint Virag, et al · 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.
Clique is hard on average for regular resolution
Albert Atserias, Ilario Bonacina, Susanna De Rezende, Massimo Lauria, Jakob Nordstrőm, and Alexander Razborov · 2018
Closest in time.
Optimal link prediction with matrix logistic regression
Nicolai Baldin and Quentin Berthet · 2018
Closest in time.
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
Closest in time.
Notes on computational-to-statistical gaps: predictions using statistical physics
Afonso S Bandeira, Amelia Perry, and Alexander S Wein · 2018
Closest in time.
Finding planted subgraphs with few eigenvalues using the schur–horn relaxation
Utkan Onur Candogan and Venkat Chandrasekaran · 2018
Closest in time.
Sherali-adams integrality gaps matching the log-density threshold
E. Chlamtáč and P. Manurangsi · 2018
Closest in time.
On finding dense common subgraphs
Moses Charikar, Yonatan Naamad, and Jimmy Wu · 2018
Closest in time.
Statistical and computational limits for sparse matrix detection
T. Tony Cai and Yihong Wu · 2018
Closest in time.