On the Spectral Properties of Symmetric FunctionsReportar como inadecuado




On the Spectral Properties of Symmetric Functions - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 CMU - Carnegie Mellon University Pittsburgh 2 LIP - Laboratoire de l-Informatique du Parallélisme 3 Chennai Mathematical Institute Inde

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.





Autor: Anil Ada - Omar Fawzi - Raghav Kulkarni -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados