Fetching the paper…
Reading the bibliography…
Using the recently developed framework of [Daniely et al, 2014], we show that under a natural assumption on the complexity of refuting random K-SAT formulas, learning DNF formulas is hard.
A machine program for theorem-proving
Martin Davis, George Logemann, and Donald Loveland · 1962
Earlier work this paper cites.
L. G. Valiant · 1984
Earlier work this paper cites.
The intractability of resolution
Armin Haken · 1985
Earlier work this paper cites.
How to construct random functions
Oded Goldreich, Shafi Goldwasser, and Silvio Micali · 1986
Earlier work this paper cites.
Computational limitations on learning from examples
L. Pitt and L.G. Valiant · 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.
When won’t membership queries help?
Dana Angluin and Michael Kharitonov · 1991
Earlier work this paper cites.
Cryptographic hardness of distribution-specific learning
Michael Kharitonov · 1993
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.
Efficient agnostic learning of neural networks with bounded fan-in
Wee Sun Lee, Peter L. Bartlett, and Robert C. Williamson · 1996
Earlier work this paper cites.
Universal portfolios with and without transaction costs
Avrim Blum and Adam Kalai · 1997
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.
Short proofs are narrow—resolution made simple
Eli Ben-Sasson and Avi Wigderson · 1999
Cited alongside, same era.
Expansion in proof complexity
Eli Ben-Sasson · 2001
Cited alongside, same era.
Some optimal inapproximability results
Johan Håstad · 2001
Cited alongside, same era.
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.
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.
Hardness of learning halfspaces with noise
V. Guruswami and P. Raghavendra · 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.
Hardness of minimizing and learning dnf expressions
Subhash Khot and Rishi Saket · 2008
Later among the works it cites.
Optimal algorithms and inapproximability results for every csp?
Prasad Raghavendra · 2008
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Uriel Feige · 2002
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.
Rank bounds and integrality gaps for cutting planes procedures
Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi · 2003
Cited alongside, same era.
Strong refutation heuristics for random k-sat
Amin Coja-Oghlan, Andreas Goerdt, and André Lanka · 2004
Cited alongside, same era.
Easily refutable subformulas of large random 3cnf formulas
Uriel Feige and Eran Ofek · 2004
Cited alongside, same era.
Towards strong nonapproximability results in the lovász-schrijver hierarchy
Mikhail Alekhnovich, Sanjeev Arora, and Iannis Tourlakis · 2005
Cited alongside, same era.
Linear level lasserre lower bounds for certain k-csps
Grant Schoenebeck · 2008
Later among the works it cites.
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.
More data speeds up training time in learning halfspaces over sparse vectors
Amit Daniely, Nati Linial, and Shai Shalev-Shwartz · 2013
Later among the works it cites.
From average case complexity to improper learning complexity
Amit Daniely, Nati Linial, and Shai Shalev-Shwartz · 2014
Closest in time.
Embedding hard learning problems into gaussian space
Adam Klivans and Pravesh Kothari · 2014
Closest in time.
Chernoff’s Inequality - A very elementary proof
N. Linial and Z. Luria · 2014
Closest in time.