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 inputs under the uniform distribution; it is not a claim that every coefficient above one fixed level vanishes.[ref]
Constant Depth Circuits, Fourier Transform, and Learnability by Nathan Linial and others. Main Lemma and learning consequences
Articles by others on the same topic
Noam Nisan is a prominent computer scientist known for his contributions to various fields within theoretical computer science, economics, and game theory. He is particularly recognized for his work on algorithmic game theory, which combines ideas from computer science and economics to understand strategic interactions in computational settings. Nisan has authored and co-authored numerous influential papers and has been involved in the development of concepts such as mechanism design and auctions within this interdisciplinary framework.