๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A simple algorithm for learning O(log n)-term DNF

โœ Scribed by Eyal Kushilevitz

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
319 KB
Volume
61
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

An O(nlog log n) Learning Algorithm for
An O(nlog log n) Learning Algorithm for DNF under the Uniform Distribution
โœ Y. Mansour ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 571 KB

We show that a DNF with terms of size at most \(d\) can be approximated by a function at most \(d^{O(d \log 1 / \epsilon)}\) nonzero Fourier coefficients such that the expected error squared, with respect to the uniform distribution, is at most \(\epsilon\). This property is used to derive a learnin