= Nathan Linial
{c}
<Nathan Linial> coauthored the 1993 Fourier analysis of <AC0> with <Yishay Mansour> and <Noam Nisan>. The paper relates constant <circuit depth> to low-level concentration of <Fourier weight>, using a switching lemma to control behavior under restrictions. This yields low-degree approximation and learning consequences. <circuit depth>, <circuit size> and approximation accuracy remain separate parameters of the bound.<Constant Depth Circuits, Fourier Transform, and Learnability by Nathan Linial and others>[abstract and Main Lemma]{ref}
Back to article page
