On the Spectral Properties of Symmetric Functions
From MaRDI portal
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.
This page was built for publication: On the Spectral Properties of Symmetric Functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6285373)
