Learning DNF in time 2Õ(n1/3)
By Adam R. Klivans, Rocco A. Servedio. 2004
176 citations recorded by the source corpus.
Subfields: Artificial Intelligence, Computational Theory and Mathematics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Tong Wang
- Cynthia Rudin
- Dennis Wei
- Oktay Günlük
- Sanjeeb Dash
- Vitaly Feldman
- Marco F. Huber
- Nadia Burkart
In Computational Theory and Mathematics
- Tong Wang
- Sanjeeb Dash
- Vitaly Feldman
- Oktay Günlük
- Dennis Wei
- Cynthia Rudin
- Allison Chang
- Margo I. Seltzer
Citations in the corpus
- Boolean Decision Rules via Column Generation (2018, background): “[47, 32, 24]) focuses on the ideal noiseless setting (sometimes allowing arbitrary queries) and is less relevant to the practice of learning compact models from noisy data.”
- Learning Optimized Or's of And's (2015, methodology): “We build OA models as a diagnostic screening tool for obstructive sleep apnea, that achieves high accuracy with a substantial gain in interpretability over other methods.”
- 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).”