Learning DNF in time 2 Õ(n 1/3 ) .

By Adam R. Klivans, Rocco A. Servedio. 2001

170 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Tong Wang
2. Cynthia Rudin
3. Finale Doshi-Velez
4. Vitaly Feldman
5. Nadia Burkart
6. Yimin Liu
7. Erica Klampfl
8. Perry MacNeille

Citations in the corpus

• New degree bounds for polynomial threshold functions (2003, methodology): “) Our upper bounds build on ideas from [14, 13] and use tools from real approximation theory.”
• Learning DNF Expressions from Fourier Spectrum (2012, background): “Despite efforts by numerous researchers, the problem still remains open, with the best algorithm taking 2Õ( 3 √ n) time (Klivans and Servedio, 2004).”
• The Sign-Rank of AC^O (2008, background): “Communication complexity has been crucial to the progress on this problem.”
• Bayesian Rule Sets for Interpretable Classification (2016, background): “[2] showed that DNFs could be learned in polynomial time in the PAC setting, and recent work has improved those bounds via polynomial threshold functions [3].”