Spectral properties of threshold functions

Craig Gotsman, Nathan Linial

Research output: Contribution to journalArticlepeer-review

34 Scopus citations

Abstract

We examine the spectra of boolean functions obtained as the sign of a real polynomial of degree d. A tight lower bound on various norms of the lower d levels of the function's Fourier transform is established. The result is applied to derive best possible lower bounds on the influences of variables on linear threshold functions. Some conjectures are posed concerning upper and lower bounds on influences of variables in higher order threshold functions.

Original languageEnglish (US)
Pages (from-to)35-50
Number of pages16
JournalCombinatorica
Volume14
Issue number1
DOIs
StatePublished - Mar 1 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

  • AMS subject classification codes (1991): 68Q15, 68R05

Fingerprint Dive into the research topics of 'Spectral properties of threshold functions'. Together they form a unique fingerprint.

Cite this