@inbook {IOPORT.06101554,
    author       = {Ada, Anil and Fawzi, Omar and Hatami, Hamed},
    title        = {Spectral norm of symmetric functions.},
    year         = {2012},
    booktitle    = {Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 15th international workshop, APPROX 2012, and 16th international workshop, RANDOM 2012, Cambridge, MA, USA, August 15--17, 2012. Proceedings},
    isbn         = {978-3-642-32511-3},
    pages        = {338-349},
    publisher    = {Berlin: Springer},
    doi          = {10.1007/978-3-642-32512-0_29},
    abstract     = {Summary: The spectral norm of a Boolean function $f:\{0,1\}^{n } \rightarrow \{ - 1,1\}$ is the sum of the absolute values of its Fourier coefficients. This quantity provides useful upper and lower bounds on the complexity of a function in areas such as learning theory, circuit complexity, and communication complexity. In this paper, we give a combinatorial characterization for the spectral norm of symmetric functions. We show that the logarithm of the spectral norm is of the same order of magnitude as $r(f)\log(n/r(f))$ where $r(f) = \max \{r _{0},r _{1}\}$, and $r _{0}$ and $r _{1}$ are the smallest integers less than $n/2$ such that $f(x)$ or $f(x) \cdot \mathrm{parity}(x)$ is constant for all $x$ with $\sum x _{i } \in [r _{0}, n - r _{1}]$. We mention some applications to the decision tree and communication complexity of symmetric functions.},
    identifier   = {06101554},
}