Proper learning of \(k\)-term DNF formulas from satisfying assignments
From MaRDI portal
Publication:2323349
DOI10.1016/j.jcss.2019.07.004zbMath1473.68102OpenAlexW2963028851WikidataQ127456128 ScholiaQ127456128MaRDI QIDQ2323349
Matthias Lutter, Maciej Liśkiewicz, K. Ruediger Reischuk
Publication date: 30 August 2019
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2019.07.004
algorithmic learning\(k\)-term DNF formulas\(q\)-bounded distributionslearning from positive examples
Cites Work
- Unnamed Item
- Unnamed Item
- Grey-box steganography
- Random generation of combinatorial structures from a uniform distribution
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- On the number of prime implicants
- On learning monotone DNF formulae under uniform distributions
- On the learnability of monotone \(k\mu\)-DNF formulae under product distributions
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- Proper learning algorithm for functions of \(k\) terms under smooth distributions.
- On learning monotone DNF under product distributions
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- When won't membership queries help?
- An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
- On the learnability of disjunctive normal form formulas
- Learning monotone log-term DNF formulas under the uniform distribution
- Queries and concept learning
- Learning from positive and unlabeled examples
- On Exact Learning Monotone DNF from Membership Queries
- Constant depth circuits, Fourier transform, and learnability
- Algorithmic Learning for Steganography: Proper Learning of k-term DNF Formulas from Positive Samples
- Learnability and the Vapnik-Chervonenkis dimension
- A theory of the learnable
- Computational limitations on learning from examples
- Learning Boolean formulas
- On the Fourier spectrum of monotone functions
- Learning from satisfying assignments
This page was built for publication: Proper learning of \(k\)-term DNF formulas from satisfying assignments
