Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SIMULTANEOUS COMMUNICATION COMPLEXITY:
Reports tagged with Simultaneous Communication Complexity:
TR15-083 | 14th May 2015
Omri Weinstein, David Woodruff

#### The Simultaneous Communication of Disjointness with Applications to Data Streams

We study $k$-party set disjointness in the simultaneous message-passing model, and show that even if each element $i\in[n]$ is guaranteed to either belong to all $k$ parties or to at most $O(1)$ parties in expectation (and to at most $O(\log n)$ parties with high probability), then \$\Omega(n \min(\log 1/\delta, \log ... more >>>

ISSN 1433-8092 | Imprint