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

Ehud Friedgut, Gil Kalai, Assaf Naor

Research output: Contribution to journalArticle

45 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 1 2002
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Applied Mathematics
  • Discrete Mathematics and Combinatorics

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