Academic Commons


Lower Bounds on Communication Complexity

Duris, Pavol; Galil, Zvi; Schnitger, Georg

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 k-round 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 k-round 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 (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.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-073-83
Published Here
October 26, 2011
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.