A slight sharpening of LMN
type: Item
instance of: scholarly article
title: A slight sharpening of LMN
zbMATH Open document ID: 1052.94506
published in: Journal of Computer and System Sciences
publication date: 2002-07-04T00:00:00Z
review text: \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.
Mathematics Subject Classification ID: 94C05
Mathematics Subject Classification ID: 68T05
Mathematics Subject Classification ID: 65T50
zbMATH DE Number: 1763398
zbMATH Keywords: constant depth circuit
zbMATH Keywords: discrete Fourier transform
zbMATH Keywords: learnability
Wikidata QID: Q56959003
author: Johan Hastad
MaRDI profile type: Publication
OpenAlex ID: W2070540961
cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures
cites work: The probabilistic method. With an appendix on the life and work of Paul Erdős.
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Constant depth circuits, Fourier transform, and learnability
cites work: An \(O(n^{\log \log n})\) learning algorithm for DNF under the uniform distribution
DOI: 10.1006/JCSS.2001.1803
description: scientific article; zbMATH DE number 1763398