Boolean functions with small spectral norm

Journal article

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.

Authors: Green, B; Sanders, T

• Journal: Geom. Funct. Anal. 18 (2008), no. 1, 144-162
• Volume: 18
• Issue: 1
• Pages: 144-162
• Publication date: 2006-05-18
• DOI: 10.1007/s00039-008-0654-y
• EISSN: 1420-8970
• ISSN: 1016-443X
• Keywords: math.CA; math.CO