Amplification of weak learning over the uniform distribution
Authors: D. Boneh and R. Lipton
Abstract:
We give a new simple proof of the Yao's XOR Theorem. In addition, we
show an application of the Theorem to learning theory.
Let F be a class of boolean functions, such as AC^0 or NC^1.
We show
that if F$ satisfies certain closure properties, then a weak
learning algorithm for
F over the uniform distribution can be amplified to a strong
learning algorithm.
Reference:
In Proceedings COLT 1993, pp. 347--351, Santa Cruz, California
Full paper: gzipped-PostScript [first posted 11/1997 ]