Boolean functions whose Fourier transform is concentrated on the first two levels

Ehud Friedgut, Gil Kalai, Assaf Naor

Research output: Contribution to journalArticlepeer-review

63 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)427-437
Number of pages11
JournalAdvances in Applied Mathematics
Volume29
Issue number3
DOIs
StatePublished - Oct 2002
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Boolean functions whose Fourier transform is concentrated on the first two levels'. Together they form a unique fingerprint.

Cite this