Title: On the Spectral Properties of Symmetric Functions,
Abstract: We characterize the approximate monomial complexity, sign monomial complexity
, and the approximate L 1 norm of symmetric functions in terms of simple
combinatorial measures of the functions. Our characterization of the
approximate L 1 norm solves the main conjecture in [AFH12]. As an application
of the characterization of the sign monomial complexity, we prove a conjecture
in [ZS09] and provide a characterization for the unbounded-error communication
complexity of symmetric-xor functions.