Yishay Mansour coauthored Constant Depth Circuits, Fourier Transform, and Learnability by Nathan Linial and others with Nathan Linial and Noam Nisan. Their analysis turns low-level concentration in the Fourier-Walsh transform into an approximation-based learning method for AC0. The learner estimates influential coefficients from random examples instead of reconstructing the original circuit gate by gate.[ref]
New to topics? Read the docs here!