𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On learning multivariate polynomials under the uniform distribution

✍ Scribed by Nader H. Bshouty

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

No coin nor oath required. For personal study only.

✦ Synopsis

We present a PAC-learning algorithm with membership queries for learning any multivariate polynomial over any finite field F under the uniform distribution. The algorithm runs in polynomial time and asks t"('~""% IF') log n queries where I is the number of terms in the polynomial, n is the number of variables and IFI is the field size. This complexity is polynomial for any fixed finite field F'. The output hypothesis is a multivariate polynomial with at most t terms. We also show that 0( log n) -multivariate polynomials (each term contains at most 0( logn) variables) are exactly learnable from membership and equivalence queries in time n"(log IF'). @ 1997 Elsevier Science B.V.

πŸ“œ 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