Title :
On communication complexity of vector-valued functions
Author :
Ahlswede, Rudolf ; Cai, Ning
Author_Institution :
Fakultat fur Math., Bielefeld Univ., Germany
fDate :
11/1/1994 12:00:00 AM
Abstract :
New upper and lower bounds on the two-way communication complexity of abstract functions g:ℋ×𝒴→𝒵 give tight bounds, when applied to vector-valued functions fn(f1 ,...,fn):ℋu×𝒴n →𝒵n, if the alphabets are small. For the set-intersection function, an optimal protocol is presented. It is based on a simple new idea applicable also to abstract functions. The two-way communication complexities of all other Boolean functions are also determined. The results are extended to meets in abstract lattices and to a probabilistic model
Keywords :
Boolean functions; communication complexity; functions; probability; protocols; set theory; vectors; Boolean functions; abstract functions; abstract lattices; alphabets; lower bounds; optimal protocol; probabilistic model; set-intersection function; two-way communication complexity; upper bounds; vector-valued functions; Boolean functions; Complexity theory; Information theory; Lattices; Linear matrix inequalities; Matrix decomposition; Protocols; Terminology; Zirconium;
Journal_Title :
Information Theory, IEEE Transactions on
