An O(n^ n) learning algorithm for DNF under the uniform distribution
From MaRDI portal
Publication:1894459
Recommendations
- Exact learning of random DNF over the uniform distribution
- On learning random DNF formulas under the uniform distribution
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- Learning monotone log-term DNF formulas under the uniform distribution
Cited in
(32)- On using the Fourier transform to learn disjoint DNF
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- A slight sharpening of LMN
- Boolean functions: influence, threshold and noise
- More efficient PAC-learning of DNF with membership queries under the uniform distribution
- On learning monotone DNF under product distributions
- Learning functions of \(k\) relevant variables
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- Fourier concentration from shrinkage
- Proper learning of \(k\)-term DNF formulas from satisfying assignments
- Learning DNF from random walks
- Optimal bounds on approximation of submodular and XOS functions by juntas
- Weakly learning DNF and characterizing statistical query learning using Fourier analysis
- The Fourier entropy-influence conjecture for certain classes of Boolean functions
- Upper bounds on Fourier entropy
- Upper bounds on Fourier entropy
- DNF sparsification and a faster deterministic counting algorithm
- Fourier bounds and pseudorandom generators for product tests
- scientific article; zbMATH DE number 7250141 (Why is no real title available?)
- Agnostically learning Boolean functions with finite polynomial representation
- Exact learning of random DNF over the uniform distribution
- Learning DNF in time
- Algorithmic Learning Theory
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Hardness amplification within NP
- Learning with maximum-entropy distributions
- Learning intersections and thresholds of halfspaces
- Testing distributional assumptions of learning algorithms
- Approximation algorithm for DNF under distributions with limited independence
- A new bound for the Fourier-entropy-influence conjecture
- A note on the entropy/influence conjecture
- On the Fourier spectrum of symmetric Boolean functions
This page was built for publication: An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1894459)
