Spectral properties of threshold functions

Craig Gotsman; Nathan Linial

doi:10.1007/BF01305949

Spectral properties of threshold functions

Craig Gotsman, Nathan Linial

Research output: Contribution to journal › Article › peer-review

40 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 language	English (US)
Pages (from-to)	35-50
Number of pages	16
Journal	Combinatorica
Volume	14
Issue number	1
DOIs	https://doi.org/10.1007/BF01305949
State	Published - Mar 1994
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Keywords

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

Access to Document

10.1007/BF01305949

Cite this

@article{6d58cfcc692140948e4904aab249aa72,

title = "Spectral properties of threshold functions",

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.",

keywords = "AMS subject classification codes (1991): 68Q15, 68R05",

author = "Craig Gotsman and Nathan Linial",

year = "1994",

month = mar,

doi = "10.1007/BF01305949",

language = "English (US)",

volume = "14",

pages = "35--50",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "1",

}

TY - JOUR

T1 - Spectral properties of threshold functions

AU - Gotsman, Craig

AU - Linial, Nathan

PY - 1994/3

Y1 - 1994/3

N2 - 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.

AB - 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.

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

UR - http://www.scopus.com/inward/record.url?scp=3142670942&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=3142670942&partnerID=8YFLogxK

U2 - 10.1007/BF01305949

DO - 10.1007/BF01305949

M3 - Article

AN - SCOPUS:3142670942

SN - 0209-9683

VL - 14

SP - 35

EP - 50

JO - Combinatorica

JF - Combinatorica

IS - 1

ER -

Spectral properties of threshold functions

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this