Amplification of weak learning over the uniform distributionAuthors: 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 ]