Fetching the paper…
Reading the bibliography…
A conjecture of Hopkins (2018) posits that for certain high-dimensional hypothesis testing problems, no polynomial-time algorithm can outperform so-called "simple statistics", which are low-degree polynomials in the data.
On the decoding of algebraic-geometric codes
Alexei N Skorobogatov and Serge G Vladut · 1990
Earlier work this paper cites.
Large cliques elude the metropolis process
Mark Jerrum · 1992
Earlier work this paper cites.
Decoding algebraic-geometric codes up to the designed minimum distance
G-L Feng and Thammavarapu RN Rao · 1993
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
Michael J. Kearns · 1993
Earlier work this paper cites.
Weakly learning DNF and characterizing statistical query learning using fourier analysis
Avrim Blum, Merrick L. Furst, Jeffrey C. Jackson, Michael J. Kearns, Yishay Mansour, and Steven Rudich · 1994
Earlier work this paper cites.
Improved decoding of reed-solomon and algebraic-geometric codes
Venkatesan Guruswami and Madhu Sudan · 1998
Earlier work this paper cites.
On representations of algebraic-geometry codes
Venkatesan Guruswami and Madhu Sudan · 2001
Earlier work this paper cites.
On the complexity of k-SAT
Russell Impagliazzo and Ramamohan Paturi · 2001
Earlier work this paper cites.
On the power of unique 2-prover 1-round games
Subhash Khot · 2002
Earlier work this paper cites.
On the unique games conjecture
Subhash Khot · 2005
Cited alongside, same era.
Message-passing algorithms for compressed sensing
David L Donoho, Arian Maleki, and Andrea Montanari · 2009
Cited alongside, same era.
On lattices, learning with errors, random linear codes, and cryptography
Oded Regev · 2009
Cited alongside, same era.
Constructions of low-degree and error-correcting ε \varepsilon -biased generators
Amir Shpilka · 2009
Cited alongside, same era.
Computational lower bounds for sparse PCA
Quentin Berthet and Philippe Rigollet · 2013
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
High-dimensional estimation via sum-of-squares proofs
Prasad Raghavendra, Tselil Schramm, and David Steurer · 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.
(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.
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.
Computational hardness of certifying bounds on constrained PCA problems
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
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
Cited alongside, same era.
Efficient bayesian estimation from few samples: community detection and related problems
Samuel B Hopkins and David Steurer · 2017
Cited alongside, same era.
Statistical Inference and the Sum of Squares Method
Samuel Hopkins · 2018
Cited alongside, same era.
Afonso S Bandeira, Dmitriy Kunisky, and Alexander S Wein · 2019
Later among the works it cites.
Algorithms for heavy-tailed statistics: Regression, covariance estimation, and beyond
Yeshwanth Cherapanamjeri, Samuel B Hopkins, Tarun Kathuria, Prasad Raghavendra, and Nilesh Tripuraneni · 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.
Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira · 2019
Later among the works it cites.
Lifting sum-of-squares lower bounds: Degree-2 to degree-4
Sidhanth Mohanty, Prasad Raghavendra, and Jeff Xu · 2019
Later among the works it cites.