Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A slight sharpening of LMN
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.ORCID iD: 0000-0002-5379-345X
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
Abstract [en]

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.
Keyword [en]
constant depth circuit, discrete Fourier transform, learnability, circuits
Identifiers
URN: urn:nbn:se:kth:diva-21389DOI: 10.1006/jcss.2001.1803ISI: 000174490900009OAI: oai:DiVA.org:kth-21389DiVA: diva2:340087
Note
QC 20100525Available from: 2010-08-10 Created: 2010-08-10 Last updated: 2017-12-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Håstad, Johan

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
Journal of computer and system sciences (Print)

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 35 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf