On the Spectral Properties of Symmetric Functions - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2017

On the Spectral Properties of Symmetric Functions

Résumé

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.
Fichier principal
Vignette du fichier
sym.pdf (151.79 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01505075 , version 1 (11-04-2017)

Identifiants

Citer

Anil Ada, Omar Fawzi, Raghav Kulkarni. On the Spectral Properties of Symmetric Functions. 2017. ⟨hal-01505075⟩
136 Consultations
112 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More