ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > AUTHORS > ANIL ADA:
All reports by Author Anil Ada:

TR08-002 | 19th December 2007
Arkadev Chattopadhyay, Anil Ada

Multiparty Communication Complexity of Disjointness

Revisions: 3
We extend the 'Generalized Discrepancy' technique suggested by Sherstov to the `Number on the Forehead' model of multiparty communication. This allows us to prove strong lower bounds of n^{\Omega(1)} on the communication needed by k players to compute the Disjointness function, provided $k$ is a constant. In general, our method ... more >>>



ISSN 1433-8092 | Imprint