Multiparty Communication Complexity

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. >

Authors

• Danny Dolev
• Tomás Feder

Keywords

• Complexity theory
• Decision trees
• Boolean functions
• Distributed computing
• Scholarships
• Very large scale integration
• Polynomials
• Complex Communication
• Multi-party Communication
• Deterministic
• Amount Of Information
• Decision Tree
• End Groups
• Input Vector
• Symmetry Breaking
• Beginning Of Phase
• Functional Complementation
• Lexicographic
• Part Of The Input
• Number Of Parties
• Increased Communication
• Boolean Function
• Execution Steps
• Number Of Processors