Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness

Andre Gronemeier
Here we prove an asymptotically optimal lower bound on the information complexity of the $k$-party disjointness function with the unique intersection promise, an important special case of the well known disjointness problem, and the AND$_k$-function in the number in the hand model. Our $\Omega(n/k)$ bound for disjointness improves on an earlier $\Omega(n/(k \log k))$ bound by Chakrabarti {\it et al.}~(2003), who obtained an asymptotically tight lower bound for one-way protocols, but failed to do so...
This data center is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.
We found no citations for this text. For information on how to provide citation information, please see our documentation.

Relation Types

  • References