Lower Bounds on Communication Complexity
 Title:
 Lower Bounds on Communication Complexity
 Author(s):
 Duris, Pavol
Galil, Zvi
Schnitger, Georg
 Date:
 1983
 Type:
 Reports
 Department(s):
 Computer Science
 Persistent URL:
 https://doi.org/10.7916/D8RN3GT3
 Series:
 Columbia University Computer Science Technical Reports
 Part Number:
 CUCS07383
 Publisher:
 Department of Computer Science, Columbia University
 Publisher Location:
 New York
 Abstract:
 We prove the following four results on communication complexity: 1) For every k ≥ 2, the language Lk 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 and can be recognized by exchanging O(k log n) bits using a simple kround protocol requires exchanging Ω(n1/2/k4log3n) bits if any (k1) round protocol is used. 2) For every k ≥ 1 and for infinitely many n ≥ 1, there exists a collection of sets Lnk ⊆ {0,1}2n that can be recognized by exchanging O(k log n) bits using a kround protocol, and any (k1)round protocol recognizing Lnk requires exchanging Ω(n/k) bits. 3) Given a set L ⊆ {0,1}2n, there is a set L ⊆{0,1}8n such that any (kround) protocol recognizing L can be transformed to a (kround) 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 recognized 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 (k1)round and kround 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.
 Subject(s):
 Computer science
 Item views
 110
 Metadata:

text  xml
 Suggested Citation:
 Pavol Duris, Zvi Galil, Georg Schnitger, 1983, Lower Bounds on Communication Complexity, Columbia University Academic Commons, https://doi.org/10.7916/D8RN3GT3.