NewEvery arXiv paper, its researchers & institutions — mapped.
paper

Boolean functions with small spectral norm

arXiv:math/0605524 · doi:10.1007/s00039-008-0654-y

Abstract

Suppose that f is a boolean function from F_2^n to {0,1} with spectral norm (that is the sum of the absolute values of its Fourier coefficients) at most M. We show that f may be expressed as +/- 1 combination of at most 2^(2^(O(M^4))) indicator functions of subgroups of F_2^n.

17 pp. Updated references.