Lower Bounds on Communication Complexity

We prove the following four results on communication complexity: 1) For every k ≥ 2, the language L k 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 k-round protocol requires exchanging Ω(n 1/2 /k 4 log 3 n) 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 L n k @@@@ {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 L n k requires exchanging Ω(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 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 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.

Authors

• Pavol Duris
• Zvi Galil
• Georg Schnitger

Keywords

No keywords are indexed for this paper.