kth.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
A slight sharpening of LMN
KTH, Tidigare Institutioner (före 2005), Numerisk analys och datalogi, NADA.ORCID-id: 0000-0002-5379-345X
2001 (Engelska)Ingår i: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 63, nr 3, s. 498-508Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
2001. Vol. 63, nr 3, s. 498-508
Nyckelord [en]
constant depth circuit, discrete Fourier transform, learnability, circuits
Identifikatorer
URN: urn:nbn:se:kth:diva-21389DOI: 10.1006/jcss.2001.1803ISI: 000174490900009Scopus ID: 2-s2.0-0035521398OAI: oai:DiVA.org:kth-21389DiVA, id: diva2:340087
Anmärkning
QC 20100525Tillgänglig från: 2010-08-10 Skapad: 2010-08-10 Senast uppdaterad: 2022-06-25Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Håstad, Johan

Sök vidare i DiVA

Av författaren/redaktören
Håstad, Johan
Av organisationen
Numerisk analys och datalogi, NADA
I samma tidskrift
Journal of computer and system sciences (Print)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 49 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf