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.[ref]
New to topics? Read the docs here!