Learning DNF Under the Uniform Distribution in Quasi-Polynomial Time.

Karsten A. Verbeurgt

Published in: COLT (1990)

Keyphrases

uniform distribution
learning dnf
dnf formulae
boolean functions
pac learning
dnf formulas
target concept
agnostic learning
membership queries
multiple instance
statistical queries
learning theory
polynomial size
term dnf
low degree
winnow algorithm