Lower Bounds on Communication Complexity
 Title:
 Lower Bounds on Communication Complexity
 Author(s):
 Duris, Pavol
Galil, Zvi
Schnitger, Georg
 Date:
 1983
 Type:
 Technical reports
 Department(s):
 Computer Science
 Persistent URL:
 http://hdl.handle.net/10022/AC:P:11575
 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 (k−1) 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 (k−1)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 (k−1)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
 97
 Metadata:

text  xml
 Suggested Citation:
 Pavol Duris, Zvi Galil, Georg Schnitger, 1983, Lower Bounds on Communication Complexity, Columbia University Academic Commons, http://hdl.handle.net/10022/AC:P:11575.