A slight sharpening of LMN
2001 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 63, no 3, 498-508 p.Article in journal (Refereed) Published
N. Linial et al. (1993. J. Assoc. Comput. Mach. 40, No. 3, 607-620) proved that a function computed by a small-depth circuit of limited size has most of its Fourier support on small sets. We improve their bounds. When the bottom fanin is bounded we use essentially their argument, but to reduce the general case to this case without a loss in the asymptotic bounds requires a new argument.
Place, publisher, year, edition, pages
2001. Vol. 63, no 3, 498-508 p.
constant depth circuit, discrete Fourier transform, learnability, circuits
IdentifiersURN: urn:nbn:se:kth:diva-21389DOI: 10.1006/jcss.2001.1803ISI: 000174490900009OAI: oai:DiVA.org:kth-21389DiVA: diva2:340087
QC 201005252010-08-102010-08-10Bibliographically approved