On Deterministic Approximation of DNF.

Michael Luby Boban Velickovic

Published in: Algorithmica (1996)

Keyphrases

boolean functions
uniform distribution
learning algorithm
relaxation algorithm
closed form
approximation algorithms
agnostic learning
membership queries
approximation error
relational databases
special case
error bounds
learning theory
pac learning
relative error
monte carlo sampling