×

A slight sharpening of LMN. (English) Zbl 1052.94506

N. Lineal, Y. Mansour and 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.

MSC:

94C05 Analytic circuit theory
68T05 Learning and adaptive systems in artificial intelligence
65T50 Numerical methods for discrete and fast Fourier transforms

Citations:

Zbl 0781.94006
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ajtai, M., \(Σ^1_1\) formulae on finite structures, Ann. Pure Appl. Logic, 24, 1-48 (1983) · Zbl 0519.03021
[2] Alon, N.; Spencer, J., The Probabilistic Method (2000), Wiley: Wiley New York
[3] Beame, P., Technical Report (1994)
[4] Furst, M.; Saxe, J.; Parity, M., Parity, circuits, and the polynomial-time hierarchy, Math. Systems Theory, 17, 13-27 (1984) · Zbl 0534.94008
[5] Håstad, J., Almost optimal lower bounds for small depth circuits, (Micali, S., Randomness and Computation. Randomness and Computation, Advances in Computing Research, 5 (1989), JAI Press: JAI Press London), 143-170
[6] Håstad, J., Computational Limitations for Small Depth Circuits (1986), MIT Press: MIT Press Cambridge
[7] Linial, N.; Mansour, Y.; Nissan, N., Constant depth circuits, Fourier transform, and learnability, J. Assoc. Comput. Mach., 40, 607-620 (1993) · Zbl 0781.94006
[8] Mansour, Y., An \(O(n^{loglogn})\) learning algorithm for DNF under the uniform distribution, J. Comput. System Sci., 50, 543-550 (1995) · Zbl 0837.68100
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.