Spectral properties of threshold functions

Craig Gotsman, Nathan Linial

Research output: Contribution to journalArticlepeer-review

39 Scopus citations


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
Issue number1
StatePublished - Mar 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


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


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

Cite this