TY - JOUR
T1 - Boolean functions whose Fourier transform is concentrated on the first two levels
AU - Friedgut, Ehud
AU - Kalai, Gil
AU - Naor, Assaf
PY - 2002/10
Y1 - 2002/10
N2 - In this note we describe Boolean functions f ( x1, x2,..., xn ) whose Fourier coefficients are concentrated on the lowest two levels. We show that such a function is close to a constant function or to a function of the form f = xk or f = 1 - xk. This result implies a "stability" version of a classical discrete isoperimetric result and has an application in the study of neutral social choice functions. The proofs touch on interesting harmonic analysis issues.
AB - In this note we describe Boolean functions f ( x1, x2,..., xn ) whose Fourier coefficients are concentrated on the lowest two levels. We show that such a function is close to a constant function or to a function of the form f = xk or f = 1 - xk. This result implies a "stability" version of a classical discrete isoperimetric result and has an application in the study of neutral social choice functions. The proofs touch on interesting harmonic analysis issues.
UR - http://www.scopus.com/inward/record.url?scp=0036821427&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0036821427&partnerID=8YFLogxK
U2 - 10.1016/S0196-8858(02)00024-6
DO - 10.1016/S0196-8858(02)00024-6
M3 - Article
AN - SCOPUS:0036821427
SN - 0196-8858
VL - 29
SP - 427
EP - 437
JO - Advances in Applied Mathematics
JF - Advances in Applied Mathematics
IS - 3
ER -