Fetching the paper…
Reading the bibliography…
The basic problem in the PAC model of computational learning theory is to determine which hypothesis classes are efficiently learnable.
A machine program for theorem-proving
Martin Davis, George Logemann, and Donald Loveland · 1962
Earlier work this paper cites.
The relative efficiency of propositional proof systems
Stephen A Cook and Robert A Reckhow · 1979
Earlier work this paper cites.
A theory of the learnable
L. G. Valiant · 1984
Earlier work this paper cites.
The intractability of resolution
Armin Haken · 1985
Earlier work this paper cites.
Computational limitations on learning from examples
L. Pitt and L.G. Valiant · 1988
Earlier work this paper cites.
The perceptron: A probabilistic model for information storage and organization in the brain
F. Rosenblatt · 1988
Earlier work this paper cites.
Cryptographic limitations on learning Boolean formulae and finite automata
Michael Kearns and Leslie G. Valiant · 1989
Earlier work this paper cites.
Constant depth circuits, Fourier transform, and learnability
Nathan Linial, Yishay Mansour, and Noam Nisan · 1989
Earlier work this paper cites.
The strength of weak learnability
R.E. Schapire · 1989
Earlier work this paper cites.
Statistical zero-knowledge languages can be recognized in two rounds
William Aiello and Johan Hastad · 1991
Earlier work this paper cites.
The hardness of approximate optima in lattices, codes, and systems of linear equations
Sanjeev Arora, László Babai, Jacques Stern, and Z Sweedyk · 1993
Earlier work this paper cites.
Cryptographic hardness of distribution-specific learning
Michael Kharitonov · 1993
Earlier work this paper cites.
Neural networks for pattern recognition
Christopher M Bishop · 1995
Earlier work this paper cites.
An o ( n log log n ) o(n\log\log n) learning algorithm for dnf under the uniform distribution
Yishay Mansour · 1995
Earlier work this paper cites.
Simplified and improved resolution lower bounds
Paul Beame and Toniann Pitassi · 1996
Earlier work this paper cites.
On relationships between statistical zero-knowledge proofs
Tatsuaki Okamoto · 1996
Cited alongside, same era.
On the complexity of unsatisfiability proofs for random k-cnf formulas
Paul Beame, Richard Karp, Toniann Pitassi, and Michael Saks · 1998
Cited alongside, same era.
Statistical Learning Theory
V. N. Vapnik · 1998
Cited alongside, same era.
Short proofs are narrow—resolution made simple
Eli Ben-Sasson and Avi Wigderson · 1999
Cited alongside, same era.
Comparing entropies in statistical zero knowledge with applications to the structure of szk
Oded Goldreich and Salil Vadhan · 1999
Cited alongside, same era.
Some optimal inapproximability results
Johan Håstad · 2001
Cited alongside, same era.
New results for learning noisy parities and halfspaces
V. Feldman, P. Gopalan, S. Khot, and A.K. Ponnuswami · 2006
Later among the works it cites.
Cryptographic hardness for learning intersections of halfspaces
Adam R. Klivans and Alexander A. Sherstov · 2006
Later among the works it cites.
On basing lower-bounds for learning on worst-case assumptions
B. Applebaum, B. Barak, and D. Xiao · 2008
Later among the works it cites.
Agnostically learning halfspaces
Adam Tauman Kalai, Adam R Klivans, Yishay Mansour, and Rocco A Servedio · 2008
Later among the works it cites.
Optimal algorithms and inapproximability results for every csp?
Prasad Raghavendra · 2008
Later among the works it cites.
Approximation resistant predicates from pairwise independence
Per Austrin and Elchanan Mossel · 2009
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Learning dnf in time 2 O ( n 1 / 3 ) 2^{O(n^{1/3})}
Adam R Klivans and Rocco Servedio · 2001
Cited alongside, same era.
Relations between average case complexity and approximation complexity
Uriel Feige · 2002
Cited alongside, same era.
On the power of unique 2-prover 1-round games
Subhash Khot · 2002
Cited alongside, same era.
Learning intersections and thresholds of halfspaces
Adam R Klivans and Ryan O’Donnell · 2002
Cited alongside, same era.
More on average case vs approximation complexity
Michael Alekhnovich · 2003
Cited alongside, same era.
Noise-tolerant learning, the parity problem, and the statistical query model
Avrim Blum, Adam Kalai, and Hal Wasserman · 2003
Cited alongside, same era.
An efficient sparse regularity concept
Amin Coja-Oghlan, Colin Cooper, and Alan Frieze · 2010
Later among the works it cites.
On the hardness of learning intersections of two halfspaces
Subhash Khot and Rishi Saket · 2011
Later among the works it cites.
Learning large-margin halfspaces with more malicious noise
P.M. Long and R.A. Servedio · 2011
Later among the works it cites.
Learning halfspaces with the zero-one loss: Time-accuracy tradeoffs
A. Birnbaum and S. Shalev-Shwartz · 2012
Later among the works it cites.
Approximation resistance on satisfiable instances for predicates strictly dominating parity
Sangxia Huang · 2012
Later among the works it cites.
On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
Boaz Barak, Guy Kindler, and David Steurer · 2013
Closest in time.
Computational lower bounds for sparse pca
Quentin Berthet and Philippe Rigollet · 2013
Closest in time.
Approximation resistance on satisfiable instances for predicates with few accepting inputs
Sangxia Huang · 2013
Closest in time.