Skip to main content

2006 | OriginalPaper | Buchkapitel

The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems

verfasst von : Richard Beigel, William Gasarch, James Glenn

Erschienen in: Mathematical Foundations of Computer Science 2006

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Let

x

i

,...,

x

k

be

n

-bit numbers and

T

 ∈ ℕ. Assume that

P

1

,...,

P

k

are players such that

P

i

knows all of the numbers

exceptx

i

. They want to determine if

$\sum^{k}_{j=1}{\it x}_{j}$

=

T

by broadcasting as few bits as possible. In [7] an upper bound of

$O(\sqrt n )$

bits was obtained for the

k

=3 case, and a lower bound of

ω

(1) for

k

≥3 when

T

=Θ(2

n

). We obtain (1) for

k

≥3 an upper bound of

$k+O((n+\log k)^{1/(\lfloor{\rm lg(2k-2)}\rfloor)})$

, (2) for

k

=3,

T

=Θ(2

n

), a lower bound of Ω(loglog

n

), (3) a generalization of the protocol to abelian groups, (4) lower bounds on the multiparty communication complexity of some regular languages, and (5) empirical results for

k

= 3.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadaten
Titel
The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems
verfasst von
Richard Beigel
William Gasarch
James Glenn
Copyright-Jahr
2006
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/11821069_13