Title :
Multiparty communication complexity
Author :
Dolev, Danny ; Feder, Tomás
Author_Institution :
Dept. of Comput. Sci., Hebrew Univ., Jerusalem, Israel
fDate :
30 Oct-1 Nov 1989
Abstract :
A given Boolean function has its input distributed among many parties. The aim is to determine which parties to talk to and what information to exchange with each of them in order to evaluate the function while minimizing the total communication. It is shown that it is possible to obtain the Boolean answer deterministically with only a polynomial increase in communication with respect to the information lower bound given by the nondeterministic communication complexity of the function
Keywords :
Boolean functions; computational complexity; Boolean function; communication complexity; information lower bound; nondeterministic communication complexity; Boolean functions; Complexity theory; Decision trees; Distributed computing; Polynomials; Scholarships; Very large scale integration;
Conference_Titel :
Foundations of Computer Science, 1989., 30th Annual Symposium on
Conference_Location :
Research Triangle Park, NC
Print_ISBN :
0-8186-1982-1
DOI :
10.1109/SFCS.1989.63514
