Fetching the paper…
Reading the bibliography…
We introduce a framework for proving lower bounds on computational problems over distributions against algorithms that can be implemented using access to a statistical query oracle.
Equations of state calculations by fast computing machines
Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller · 1953
Earlier work this paper cites.
Monte carlo sampling methods using markov chains and their applications
W. K. Hastings · 1970
Earlier work this paper cites.
On the uniform convergence of relative frequencies of events to their probabilities
V. Vapnik and A. Chervonenkis · 1971
Earlier work this paper cites.
Maximum likelihood from incomplete data via the em algorithm
A. P. Dempster, N. M. Laird, and D. B. Rubin · 1977
Earlier work this paper cites.
Probabilistic computations: Toward a unified measure of complexity
Andrew Yao · 1977
Earlier work this paper cites.
Probabilistic analysis of graph-theoretic algorithms
R. Karp · 1979
Earlier work this paper cites.
Optimization by simmulated annealing
Scott Kirkpatrick, D. Gelatt Jr., and Mario P. Vecchi · 1983
Earlier work this paper cites.
A theory of the learnable
Leslie G. Valiant · 1984
Earlier work this paper cites.
Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm
V. Černý · 1985
Earlier work this paper cites.
The calculation of posterior distributions by data augmentation (with discussion)
M Tanner and W Wong · 1987
Earlier work this paper cites.
Sampling based approaches to calculating marginal densities
A. E. Gelfand and A. F. M. Smith · 1990
Earlier work this paper cites.
Large cliques elude the metropolis process
Mark Jerrum · 1992
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.
Expected complexity of graph partitioning problems
Ludek Kucera · 1995
Earlier work this paper cites.
Local search strategies for satisfiability testing
Bart Selman, Henry Kautz, and Bram Cohen · 1995
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.
Learning with restricted focus of attention
Shai Ben-David and Eli Dichterman · 1998
Earlier work this paper cites.
A polynomial-time algorithm for learning noisy linear threshold functions
Avrim Blum, Alan M. Frieze, Ravi Kannan, and Santosh Vempala · 1998
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
M. Kearns · 1998
Earlier work this paper cites.
Finding and certifying a large hidden clique in a semirandom graph
U. Feige and R. Krauthgamer · 2000
Earlier work this paper cites.
Hiding cliques for cryptographic security
Ari Juels and Marcus Peinado · 2000
Earlier work this paper cites.
Computational sample complexity and attribute-efficient learning
R. Servedio · 2000
Earlier work this paper cites.
Some optimal inapproximability results
Johan Håstad · 2001
Earlier work this paper cites.
Spectral partitioning of random graphs
F. McSherry · 2001
Cited alongside, same era.
On learning correlated boolean functions using statistical queries
Ke Yang · 2001
Cited alongside, same era.
Rademacher and Gaussian complexities: Risk bounds and structural results
P. Bartlett and S. Mendelson · 2002
Cited alongside, same era.
Relations between average case complexity and approximation complexity
Uriel Feige · 2002
Cited alongside, same era.
The probable value of the Lovász–Schrijver relaxations for maximum independent set
Uriel Feige and Robert Krauthgamer · 2003
Cited alongside, same era.
Ruling out ptas for graph min-bisection, densest subgraph and bipartite clique
Subhash Khot · 2004
Cited alongside, same era.
Finding hidden cliques in linear time with high probability
Y. Dekel, O. Gurel-Gurevich, and Y. Peres · 2011
Later among the works it cites.
How hard is it to approximate the best nash equilibrium?
Elad Hazan and Robert Krauthgamer · 2011
Later among the works it cites.
What can we learn privately?
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith · 2011
Later among the works it cites.
Polynomial integrality gaps for strong sdp relaxations of densest k
Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, and Yuan Zhou · 2012
Closest in time.
A complete characterization of statistical query learning with applications to evolvability
V. Feldman · 2012
Closest in time.
Complexity theoretic lower bounds for sparse principal component detection
Quentin Berthet and Philippe Rigollet · 2013
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Practical privacy: the SuLQ framework
A. Blum, C. Dwork, F. McSherry, and K. Nissim · 2005
Cited alongside, same era.
New lower bounds for statistical query learning
Ke Yang · 2005
Cited alongside, same era.
Map-reduce for machine learning on multicore
C. Chu, S. Kim, Y. Lin, Y. Yu, G. Bradski, A. Ng, and K. Olukotun · 2006
Cited alongside, same era.
Testing k-wise and almost k-wise independence
N. Alon, A. Andoni, T. Kaufman, K. Matulef, R. Rubinfeld, and N. Xie · 2007
Cited alongside, same era.
A simple polynomial-time rescaling algorithm for solving linear programs
John Dunagan and Santosh Vempala · 2008
Cited alongside, same era.
Evolvability from learning algorithms
V. Feldman · 2008
Cited alongside, same era.
Closest in time.
Finding hidden cliques of size \sqrt{N/e} in nearly linear time
Yash Deshpande and Andrea Montanari · 2013
Closest in time.
Computational barriers in minimax submatrix detection
Zongming Ma and Yihong Wu · 2013
Closest in time.
Information-theoretic lower bounds for distributed statistical estimation with communication constraints
Yuchen Zhang, John C. Duchi, Michael I. Jordan, and Martin J. Wainwright · 2013
Closest in time.
Structure learning of antiferromagnetic ising models
Guy Bresler, David Gamarnik, and Devavrat Shah · 2014
Closest in time.
On the hardness of signaling
Shaddin Dughmi · 2014
Closest in time.
Open problem: The statistical query complexity of learning sparse halfspaces
Vitaly Feldman · 2014
Closest in time.
Sparse CCA: Adaptive Estimation and Computational Barriers
C. Gao, Z. Ma, and H. H. Zhou · 2014
Closest in time.
Statistical and computational trade-offs in estimation of sparse principal components
T. Wang, Q. Berthet, and R. J. Samworth · 2014
Closest in time.
Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
T. T. Cai, T. Liang, and A. Rakhlin · 2015
Closest in time.
Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems
Yash Deshpande and Andrea Montanari · 2015
Closest in time.
On the complexity of random satisfiability problems with planted solutions
Vitaly Feldman, Will Perkins, and Santosh Vempala · 2015
Closest in time.
Statistical query algorithms for stochastic convex optimization
Vitaly Feldman, Cristobal Guzman, and Santosh Vempala · 2015
Closest in time.
Computational lower bounds for community detection on random graphs
Bruce E. Hajek, Yihong Wu, and Jiaming Xu · 2015
Closest in time.
Sum-of-squares lower bounds for planted clique
R. Meka, A. Potechin, and A. Wigderson · 2015
Closest in time.
Minimax rates for memory-bounded sparse linear regression
Jacob Steinhardt and John C. Duchi · 2015
Closest in time.
A general characterization of the statistical query complexity
Vitaly Feldman · 2016
Closest in time.
Memory, communication, and statistical queries
J. Steinhardt, G. Valiant, and S. Wager · 2016
Closest in time.