Fetching the paper…
Reading the bibliography…
Inference problems with conjectured statistical-computational gaps are ubiquitous throughout modern statistics, computer science and statistical physics.
The generalised product moment distribution in samples from a normal multivariate population
John Wishart · 1928
Earlier work this paper cites.
A robust version of the probability ratio test
Peter J Huber · 1965
Earlier work this paper cites.
Mathematics and the picturing of data
John W Tukey · 1975
Earlier work this paper cites.
Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane
Richard M Karp · 1977
Earlier work this paper cites.
Expected behavior of graph coloring algorithms
L Kučera · 1977
Earlier work this paper cites.
Estimating mixtures of normal distributions and switching regressions
Richard E Quandt and James B Ramsey · 1978
Earlier work this paper cites.
Multivariate analysis
K. V. Mardia, J. T. Kent, and J. M. Bibby · 1979
Earlier work this paper cites.
Finite exchangeable sequences
Persi Diaconis and David Freedman · 1980
Earlier work this paper cites.
The eigenvalues of random symmetric matrices
Zoltán Füredi and János Komlós · 1981
Earlier work this paper cites.
Stochastic blockmodels: First steps
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt · 1983
Earlier work this paper cites.
A theory of the learnable
Leslie G Valiant · 1984
Earlier work this paper cites.
Rates of convergence of minimum distance estimators and kolmogorov’s entropy
Yannis G Yatracos · 1985
Earlier work this paper cites.
Average case complete problems
Leonid A Levin · 1986
Earlier work this paper cites.
Graph bisection algorithms with good average case behavior
Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, and Michael Sipser · 1987
Earlier work this paper cites.
Eigenvalues and graph bisection: An average-case analysis
Ravi B Boppana · 1987
Earlier work this paper cites.
The solution of some random np-hard problems in polynomial expected time
Martin E. Dyer and Alan M. Frieze · 1989
Earlier work this paper cites.
Mixtures of linear regressions
Richard D De Veaux · 1989
Earlier work this paper cites.
Robust estimation of a location parameter
Peter J Huber · 1992
Earlier work this paper cites.
Locality in distributed graph algorithms
Nathan Linial · 1992
Earlier work this paper cites.
Random-self-reducibility of complete sets
Joan Feigenbaum and Lance Fortnow · 1993
Earlier work this paper cites.
Hierarchical mixtures of experts and the em algorithm
Michael I Jordan and Robert A Jacobs · 1994
Earlier work this paper cites.
Coloring random and semi-random k-colorable graphs
Avrim Blum and Joel Spencer · 1995
Earlier work this paper cites.
A mixture likelihood approach for generalized linear models
Michel Wedel and Wayne S DeSarbo · 1995
Earlier work this paper cites.
Regression shrinkage and selection via the lasso
Robert Tibshirani · 1996
Earlier work this paper cites.
Natural proofs
Alexander A Razborov and Steven Rudich · 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.
Computational sample complexity and attribute-efficient learning
Rocco A Servedio · 1999
Earlier work this paper cites.
Computational sample complexity
Scott E Decatur, Oded Goldreich, and Dana Ron · 2000
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.
Algorithms for graph partitioning on the planted partition model
Anne Condon and Richard M Karp · 2001
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.
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.
Max cut for random graphs with a planted partition
Béla Bollobás and Alex D Scott · 2004
Earlier work this paper cites.
Sparse principal components analysis
Iain M Johnstone and Arthur Yu Lu · 2004
Earlier work this paper cites.
Finite mixture models
Geoffrey J McLachlan and David Peel · 2004
Earlier work this paper cites.
Hypothesis testing in mixture regression models
Hong-Tu Zhu and Heping Zhang · 2004
Earlier work this paper cites.
Spectral techniques applied to sparse random graphs
Uriel Feige and Eran Ofek · 2005
Earlier work this paper cites.
Robust regression and outlier detection
Peter J Rousseeuw and Annick M Leroy · 2005
Earlier work this paper cites.
Spectral norm of random matrices
Van H Vu · 2005
Earlier work this paper cites.
Pattern recognition and machine learning
Christopher M Bishop · 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.
Average-case complexity
Andrej Bogdanov, Luca Trevisan, et al · 2006
Earlier work this paper cites.
Variable selection for model-based clustering
Adrian E Raftery and Nema Dean · 2006
Earlier work this paper cites.
Sparse principal component analysis
Hui Zou, Trevor Hastie, and Robert Tibshirani · 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 phase transition in inhomogeneous random graphs
Béla Bollobás, Svante Janson, and Oliver Riordan · 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.
Penalized model-based clustering with application to variable selection
Wei Pan and Xiaotong Shen · 2007
Earlier work this paper cites.
On basing lower-bounds for learning on worst-case assumptions
Benny Applebaum, Boaz Barak, and David Xiao · 2008
Earlier work this paper cites.
Algorithmic barriers from phase transitions
Dimitris Achlioptas and Amin Coja-Oghlan · 2008
Earlier work this paper cites.
The tradeoffs of large scale learning
Léon Bottou and Olivier Bousquet · 2008
Earlier work this paper cites.
On the constant-depth complexity of k-clique
Benjamin Rossman · 2008
Earlier work this paper cites.
Simultaneous analysis of lasso and dantzig selector
Peter J Bickel, Ya’acov Ritov, and Alexandre B Tsybakov · 2009
Earlier work this paper cites.
Expression quantitative trait loci mapping with multivariate sparse partial least squares regression
Hyonho Chun and Sündüz Keles · 2009
Earlier work this paper cites.
Image compression by sparse pca coding in curvelet domain
A Majumdar · 2009
Earlier work this paper cites.
Variable selection for clustering with gaussian mixture models
Cathy Maugis, Gilles Celeux, and Marie-Laure Martin-Magniette · 2009
Earlier work this paper cites.
Sparse canonical correlation analysis with application to genomic data integration
Elena Parkhomenko, David Tritchler, and Joseph Beyene · 2009
Earlier work this paper cites.
Using evidence of mixed populations to select variables for clustering very high-dimensional data
Yao-ban Chan and Peter Hall · 2010
Earlier work this paper cites.
Graph partitioning via adaptive spectral techniques
Amin Coja-Oghlan · 2010
Earlier work this paper cites.
Public-key encryption schemes with auxiliary inputs
Yevgeniy Dodis, Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, and Vinod Vaikuntanathan · 2010
Earlier work this paper cites.
Finding hidden cliques in linear time
Uriel Feige and Dorit Ron · 2010
Earlier work this paper cites.
Fitting mixtures of linear regressions
Susana Faria and Gilda Soromenho · 2010
Earlier work this paper cites.
Robustness of the learning with errors assumption
Shafi Goldwasser, Yael Kalai, Chris Peikert, and Vinod Vaikuntanathan · 2010
Earlier work this paper cites.
Correlation clustering with noisy input
Claire Mathieu and Warren Schudy · 2010
Earlier work this paper cites.
Restricted eigenvalue properties for correlated gaussian designs
Garvesh Raskutti, Martin J Wainwright, and Bin Yu · 2010
Earlier work this paper cites.
ℓ 1 \ell_{1} -penalization for mixture regression models
Nicolas Städler, Peter Bühlmann, and Sara Van De Geer · 2010
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.
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.
Notes on Levin’s theory of average-case complexity
Oded Goldreich · 2011
Earlier work this paper cites.
Robust statistics
Peter J Huber · 2011
Earlier work this paper cites.
How to play unique games against a semi-random adversary: Study of semi-random models of unique games
Alexandra Kolla, Konstantin Makarychev, and Yury Makarychev · 2011
Earlier work this paper cites.
A non asymptotic penalized criterion for gaussian mixture model selection
Cathy Maugis and Bertrand Michel · 2011
Earlier work this paper cites.
Spectral clustering and the high-dimensional stochastic blockmodel
Karl Rohe, Sourav Chatterjee, Bin Yu, et al · 2011
Earlier work this paper cites.
Spectral clustering of graphs with general degrees in the extended planted partition model
Kamalika Chaudhuri, Fan Chung, and Alexander Tsiatas · 2012
Earlier work this paper cites.
Clustering sparse graphs
Yudong Chen, Sujay Sanghavi, and Huan Xu · 2012
Earlier work this paper cites.
Approximation algorithms for semi-random partitioning problems
Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan · 2012
Earlier work this paper cites.
Graph spectra and the detectability of community structure in networks
Raj Rao Nadakuditi and Mark EJ Newman · 2012
Cited alongside, same era.
Minimax theory for high-dimensional gaussian mixtures with sparse mean separation
Martin Azizyan, Aarti Singh, and Larry Wasserman · 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
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.
Robust sparse regression under adversarial corruption
Yudong Chen, Constantine Caramanis, and Shie Mannor · 2013
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.
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.
The landscape of the spiked tensor model
Gerard Ben Arous, Song Mei, Andrea Montanari, and Mihai Nica · 2017
Later among the works it cites.
Statistical guarantees for the em algorithm: From population to sample-based analysis
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Computational and statistical tradeoffs via convex relaxation
Venkat Chandrasekaran and Michael I Jordan · 2013
Cited alongside, same era.
Spectral experts for estimating mixtures of linear regressions
Arun Tejasvi Chaganty and Percy Liang · 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.
Bayesian data analysis
Andrew Gelman, John B Carlin, Hal S Stern, David B Dunson, Aki Vehtari, and Donald B Rubin · 2013
Cited alongside, same era.
Spectra of edge-independent random graphs
Linyuan Lu and Xing Peng · 2013
Cited alongside, same era.
Sparse signal recovery from quadratic measurements via convex programming
Xiaodong Li and Vladislav Voroninski · 2013
Cited alongside, same era.
Sivaraman Balakrishnan, Martin J Wainwright, Bin Yu, et al · 2017
Later among the works it cites.
Learning from untrusted data
Moses Charikar, Jacob Steinhardt, and Gregory Valiant · 2017
Later among the works it cites.
Distributed statistical machine learning in adversarial settings: Byzantine gradient descent
Yudong Chen, Lili Su, and Jiaming Xu · 2017
Later among the works it cites.
Convex and nonconvex formulations for mixed regression with two components: Minimax optimal rates
Yudong Chen, Xinyang Yi, and Constantine Caramanis · 2017
Later among the works it cites.
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.
Sparse cca: Adaptive estimation and computational barriers
Chao Gao, Zongming Ma, and Harrison H Zhou · 2017
Later among the works it cites.
Limits of local algorithms over sparse random graphs
David Gamarnik, Madhu Sudan, et al · 2017
Later among the works it cites.
High dimensional regression with binary coefficients. estimating squared error and a phase transtition
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
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.
Concentration and regularization of random graphs
Can M Le, Elizaveta Levina, and Roman Vershynin · 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.
The computer science and physics of community detection: Landscapes, phase transitions, and hardness
Cristopher Moore · 2017
Later among the works it cites.
A semidefinite program for unbalanced multisection in the stochastic block model
Amelia Perry and Alexander S Wein · 2017
Later among the works it cites.
Detection and feature selection in sparse mixture models
Nicolas Verzelen and Ery Arias-Castro · 2017
Later among the works it cites.
Sparse phase retrieval via truncated amplitude flow
Gang Wang, Liang Zhang, Georgios B Giannakis, Mehmet Akçakaya, and Jie Chen · 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.
Proof of the achievability conjectures for the general stochastic block model
Emmanuel Abbe and Colin Sandon · 2018
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.
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.
Finding planted subgraphs with few eigenvalues using the schur–horn relaxation
Utkan Onur Candogan and Venkat Chandrasekaran · 2018
Later among the works it cites.
Phase transition in random tensors with multiple spikes
Wei-Kuo Chen, Madeline Handschy, and Gilad Lerman · 2018
Later among the works it cites.
Recovering asymmetric communities in the stochastic block model
Francesco Caltagirone, Marc Lelarge, and Léo Miolane · 2018
Later among the works it cites.
Statistical and computational limits for sparse matrix detection
T. Tony Cai and Yihong Wu · 2018
Later among the works it cites.
Robustly learning a gaussian: Getting optimal error, efficiently
Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart · 2018
Later among the works it cites.
Curse of heterogeneity: Computational barriers in sparse mixture models and phase retrieval
Jianqing Fan, Han Liu, Zhaoran Wang, and Zhuoran Yang · 2018
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 · 2018
Later among the works it cites.
Phase retrieval under a generative prior
Paul Hand, Oscar Leong, and Vlad Voroninski · 2018
Later among the works it cites.
Statistical Inference and the Sum of Squares Method
Samuel B 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.
Efficient algorithms for outlier-robust regression
Adam Klivans, Pravesh K Kothari, and Raghu Meka · 2018
Later among the works it cites.
Learning mixtures of linear regressions with nearly optimal complexity
Yuanzhi Li and Yingyu Liang · 2018
Later among the works it cites.
High dimensional robust sparse regression
Liu Liu, Yanyao Shen, Tianyang Li, and Constantine Caramanis · 2018
Later among the works it cites.
Fundamental limits of weak recovery with applications to phase retrieval
Marco Mondelli and Andrea Montanari · 2018
Later among the works it cites.
On the connection between learning two-layers neural networks and tensor decomposition
Marco Mondelli and Andrea Montanari · 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.
Robust estimation via robust gradient estimation
Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar · 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.
Clustering semi-random mixtures of gaussians
Aravindan Vijayaraghavan and Pranjal Awasthi · 2018
Later among the works it cites.
Statistical problems with planted structures: Information-theoretical and computational limits
Yihong Wu and Jiaming Xu · 2018
Later among the works it cites.
Learning mixtures of sparse linear regressions using sparse graph codes
Dong Yin, Ramtin Pedarsani, Yudong Chen, and Kannan Ramchandran · 2018
Later among the works it cites.
Average-case lower bounds for learning sparse mixtures, robust estimation and semirandom adversaries
Matthew Brennan and Guy Bresler · 2019
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.
Universality of computational lower bounds for submatrix detection
Matthew Brennan, Guy Bresler, and Wasim Huleihel · 2019
Later among the works it cites.
Phase transitions for detecting latent geometry in random graphs
Matthew Brennan, Guy Bresler, and Dheeraj Nagaraj · 2019
Later among the works it cites.
Optimal errors and phase transitions in high-dimensional generalized linear models
Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, and Lenka Zdeborová · 2019
Later among the works it cites.
Computational hardness of certifying bounds on constrained pca problems
Afonso S Bandeira, Dmitriy Kunisky, and Alexander S Wein · 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, Mustazee Rahman, et al · 2019
Later among the works it cites.
Phase transition in the spiked random tensor with rademacher prior
Wei-Kuo Chen · 2019
Later among the works it cites.
The middle-scale asymptotics of wishart matrices
Didier Chételat, Martin T Wells, et al · 2019
Later among the works it cites.
Quantum entropy scoring for fast robust mean estimation and improved outlier detection
Yihe Dong, Samuel Hopkins, and Jerry Li · 2019
Later among the works it cites.
Sever: A robust meta-algorithm for stochastic optimization
Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stewart · 2019
Later among the works it cites.
Efficient algorithms and lower bounds for robust linear regression
Ilias Diakonikolas, Weihao Kong, and Alistair Stewart · 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.
How hard is robust mean estimation?
Samuel B Hopkins and Jerry Li · 2019
Later among the works it cites.
List-decodable linear regression
Sushrut Karmalkar, Adam Klivans, and Pravesh Kothari · 2019
Later among the works it cites.
Sample complexity of learning mixture of sparse linear regressions
Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, and Soumyabrata Pal · 2019
Later among the works it cites.
A survey of leakage-resilient cryptography
Yael Tauman Kalai and Leonid Reyzin · 2019
Later among the works it cites.
Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira · 2019
Later among the works it cites.
High dimensional robust estimation of sparse models via trimmed hard thresholding
Liu Liu, Tianyang Li, and Constantine Caramanis · 2019
Later among the works it cites.
Lifting sum-of-squares lower bounds: Degree- 2 2 to degree- 4 4
Sidhanth Mohanty, Prasad Raghavendra, and Jeff Xu · 2019
Later among the works it cites.
Complex energy landscapes in spiked-tensor and simple glassy models: Ruggedness, arrangements of local minima, and phase transitions
Valentina Ros, Gerard Ben Arous, Giulio Biroli, and Chiara Cammarota · 2019
Later among the works it cites.
A smooth transition from wishart to goe
Miklós Z Rácz and Jacob Richey · 2019
Later among the works it cites.
Typology of phase transitions in Bayesian inference problems
Federico Ricci-Tersenghi, Guilhem Semerjian, and Lenka Zdeborová · 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.
The estimation error of general first order methods
Michael Celentano, Andrea Montanari, and Yuchen Wu · 2020
Closest in time.
Robust regression via mutivariate regression depth
Chao Gao · 2020
Closest in time.
Counterexamples to the low-degree conjecture
Justin Holmgren and Alexander Wein · 2020
Closest in time.
Statistical limits of spiked tensor models
Amelia Perry, Alexander S Wein, Afonso S Bandeira, et al · 2020
Closest in time.
List decodable learning via sum of squares
Prasad Raghavendra and Morris Yau · 2020
Closest in time.