Lower bounds on communication complexity
In: Information and Computation, Jg. 73 (1987-04-01), Heft 1, S. 1-22
Online
unknown
Zugriff:
We prove the following four results on communication complexity: (1) For every k ≥ 2, the language of encodings of directed graphs of out-degree one that contain a path of length k + 1 from the first vertex to the last vertex can be recognized by exchanging O(k log n)1 bits using a simple k-round protocol and requires the exchange of Ω( n 1 2 (k 4 log 3 n) ) bits by any (k − 1)-round protocol. (2) For every k ≥ 1 and for infinitely many n ≥ 1, there exists a collection of sets Lkn ⊆ {0, 1}2n that can be recognized by exchanging O(k log n) bits using a k-round protocol, and any (k − 1)-round protocol recognizing Lkn requires the exchange of Ω( n k ) bits. (3) Given a set L ⊆ {0, 1}2n, there is a set L ⊆ {0, 1} 8n such that any (k-round) protocol recognizing L can be transformed to a (k-round) fixed-partition protocol recognizing L with the same communication complexity, and vice versa. (4) For every integer function f, 1 ≤ f(n) ≤ n, there are languages recognizable by a one-round deterministic protocol exchanging f(n) bits, but not by any nondeterministic protocol exchanging f(n) − 1 bits. The first two results show in an incomparable way an exponential gap between (k − 1)-round and k-round protocols, settling a conjecture by Papadimitriou and Sipser. The third result shows that as long as we are interested in existence proofs, a fixed partition of the input is not a restriction. The fourth result extends a result by Papadimitriou and Sipser who showed that for every integer function f, 1 ≤ f(n) ≤ n, there is a language accepted by a deterministic protocol exchanging f(n) bits but not by any deterministic protocol exchanging f(n) − 1 bits.
Titel: |
Lower bounds on communication complexity
|
---|---|
Autor/in / Beteiligte Person: | Duris, Pavol ; Schnitger, Georg ; Galil, Zvi |
Link: | |
Zeitschrift: | Information and Computation, Jg. 73 (1987-04-01), Heft 1, S. 1-22 |
Veröffentlichung: | Elsevier BV, 1987 |
Medientyp: | unknown |
ISSN: | 0890-5401 (print) |
DOI: | 10.1016/0890-5401(87)90037-x |
Schlagwort: |
|
Sonstiges: |
|