| Boolean functions whose Fourier transform is concentrated on the first two levels (2008) | |||||||||||||||
Abstract | |||||||||||||||
| 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 \Gamma 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. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||