A slight sharpening of LMN (Q1604204)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A slight sharpening of LMN |
scientific article; zbMATH DE number 1763398
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A slight sharpening of LMN |
scientific article; zbMATH DE number 1763398 |
Statements
A slight sharpening of LMN (English)
0 references
4 July 2002
0 references
\textit{N. Lineal}, \textit{Y. Mansour} and \textit{N. Nisan} [J. Assoc. Comput. Math. 40, 607--620 (1993; Zbl 0781.94006)] 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.
0 references
constant depth circuit
0 references
discrete Fourier transform
0 references
learnability
0 references
