Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness

André Gronemeier
  • Fonction : Auteur
  • PersonId : 857950

Résumé

Here we prove an asymptotically optimal lower bound on the information complexity of the k-party disjointness function with the unique intersection promise, an important special case of the well known disjointness problem, and the ANDk-function in the number in the hand model. Our (n/k) bound for disjointness improves on an earlier (n/(k log k)) bound by Chakrabarti et al. (2003), who obtained an asymptotically tight lower bound for one-way protocols, but failed to do so for the general case. Our result eliminates both the gap between the upper and the lower bound for unrestricted protocols and the gap between the lower bounds for one-way protocols and unrestricted protocols.
Fichier principal
Vignette du fichier
gronemeier_new.pdf (258.15 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00359840 , version 1 (09-02-2009)

Identifiants

  • HAL Id : inria-00359840 , version 1
  • ARXIV : 0902.1609

Citer

André Gronemeier. Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.505-516. ⟨inria-00359840⟩

Collections

STACS2009
38 Consultations
89 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More