Browse Prior Art Database

LOWER BOUNDS ON COMMUNICATION COMPLEXITY

IP.com Disclosure Number: IPCOM000127978D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 28 page(s) / 57K

Publishing Venue

Software Patent Institute

Related People

Pavol Duris: AUTHOR [+5]

Abstract

We prove the following four results on communication complexity:

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 28

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

LOWER BOUNDS ON COMMUNICATION COMPLEXITY

Pavol Duris* Slovak Academy of Science

Zvi Galil* Department of Computer Science Columbia University Tel-Aviv University

Georg Schnitger Department of Computer Science Penn State University

October 1983

*Research supported by National Science Foundation Grant MCS-83 0313 9

>

Abstract

We prove the following four results on communication complexity:

1) For every k 2 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 0(k log n) bits using a simple k-round protocol requires exchanging

(Equation Omitted)

bits if any (k-1)-round protocol is used. 2) For every k 2 1 and for infinitely many n 2 1, there exists a collection of sets

(Equation Omitted)

that can be recognized by exchanging 0(k log n)**bits using a k-round protocol, and any (k-1)- round protocol recognizing Lk requires exchanging 0(n/k) bits. 3) Given a set

(Equation Omitted)

, there is a set L c(0,1)8n such that any (k-round) protocol recognizing L can be trans- formed to a (k-round) fixed partition protocol recognizing L with the same communication complexity, and vice versa.

4) For every integer function

(Equation Omitted)

, there are languages recognized by a one round deterministic protocol exchanging f(n) bits, but not by any nondetermin-istic protocol exchanging f(n) - 1 bits.

*All logarithms in the paper are of base 2.

Columbia University Page 1 Dec 31, 1983

Page 2 of 28

LOWER BOUNDS ON COMMUNICATION COMPLEXITY

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 res-triction. The fourth result extends a result by Papadimitriou and Sipser who showed that for every integer function

(Equation Omitted)

, there is a language accepted by a deterministic protocol exchanging f(n) bits but: not by any deterministic protocol exchanging f(n) - 1 bits. 0. Introduction Suppose that a language L E {0,1}* must be recognized by two distant computers. Each computer receives half of the input bits, and the computation proceeds using some protocol for communication between the two computers. The minimum number of bits that has to be exchanged in order to success-fully recognize

(Equation Omitted)

, minimized over all partitions of the input bits into two equal parts, and considered as a function of n, is called the communication complexity of L. This model was suggested by Papadimitriou and Sipser - [1]. They motivated it by pointing out its relation to lower bound proofs in VLSI [2,3,4]. A closely related model, where the partition of the input is fixed was studied in [5,6]. Both versions were also studied in [7,8].

We now review...