Name
Abstract | ||
|---|---|---|
In this note we describe Boolean functions f(x"1,x"2,...,x"n) 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=x"k or f=1-x"k. 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. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1016/S0196-8858(02)00024-6 | Advances in Applied Mathematics |
Keywords | Field | DocType |
boolean function,interesting harmonic analysis issue,fourier coefficient,proofs touch,neutral social choice function,constant function,classical discrete isoperimetric result,harmonic analysis,social choice,fourier transform | Boolean function,Discrete mathematics,Combinatorics,Fourier analysis,Of the form,Mathematical analysis,Constant function,Fourier transform,Harmonic analysis,Fourier series,Isoperimetric inequality,Mathematics | Journal |
Volume | Issue | ISSN |
29 | 3 | 0196-8858 |
Citations | PageRank | References |
34 | 4.74 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ehud Friedgut | 1 | 440 | 38.93 |
| Gil Kalai | 2 | 469 | 68.53 |
| Assaf Naor | 3 | 750 | 64.06 |