= Noam Nisan
{c}
<Noam Nisan> coauthored the 1993 analysis of constant-depth circuits with <Nathan Linial> and <Yishay Mansour>. Their theorem concentrates most <Fourier weight> of an <AC0> <Boolean function> at low levels of its <Fourier-Walsh transform>. This permits approximation and learning from sampled <input>[inputs] under the <discrete uniform distribution>[uniform distribution]; it is not a claim that every coefficient above one fixed level vanishes.<Constant Depth Circuits, Fourier Transform, and Learnability by Nathan Linial and others>[Main Lemma and learning consequences]{ref}
Back to article page
