Boolean functions with small spectral norm, revisited

Abstract

We show that if $f$ is an integer-valued function with spectral norm at most $M$ then there are subspaces $V_1,\dots ,V_L$ and signs ${\sigma }_1,\dots ,{\sigma }_L\in \{-1,1\}$ such that $f={\sigma }_1{1}_{V_1}+\cdots +{\sigma }_L{1}_{V_L}$ where $L<\exp (M^{3+o(1)})$. This note extracts out the argument from arXiv:1610.07092 to the model setting of ${\mathbb{F}}_2^n$. The hope is that it will clarify the arguments of that paper.

11 pp, corrected some errors

References in corpus (3)

• The structure theory of set addition revisited
• Bounds in Cohen's idempotent theorem
• Spectral Norm of Symmetric Functions

Cited by in corpus (1)

• Bounds in Cohen's idempotent theorem