Amplification of weak learning over the uniform distribution

Authors: D. Boneh and R. Lipton

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.

In Proceedings COLT 1993, pp. 347--351, Santa Cruz, California

Full paper: gzipped-PostScript         [first posted 11/1997 ]