An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution

DOI10.1006/jcss.1995.1043zbMath0837.68100OpenAlexW3148810677MaRDI QIDQ1894459

Yishay Mansour

Publication date: 15 August 1995

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1995.1043

zbMATH Keywords

learning algorithm

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Related Items (19)

Boolean functions: influence, threshold and noise ⋮ On learning monotone DNF under product distributions ⋮ Learning functions of \(k\) relevant variables ⋮ Upper bounds on Fourier entropy ⋮ Upper Bounds on Fourier Entropy ⋮ DNF sparsification and a faster deterministic counting algorithm ⋮ Learning intersections and thresholds of halfspaces ⋮ The Fourier Entropy–Influence Conjecture for Certain Classes of Boolean Functions ⋮ Fourier concentration from shrinkage ⋮ A note on the entropy/influence conjecture ⋮ On the Fourier spectrum of symmetric Boolean functions ⋮ Hardness amplification within NP ⋮ Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas ⋮ Unnamed Item ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ Proper learning of \(k\)-term DNF formulas from satisfying assignments ⋮ Learning DNF from random walks ⋮ A slight sharpening of LMN ⋮ Agnostically Learning Boolean Functions with Finite Polynomial Representation

This page was built for publication: An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution