# 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 ]