Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information

Details Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information

2009-02-10

arxiv.org/abs/0902.1609v1

26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (2009) 505-516

Computer Science

Computational Complexity

Scientific paper

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 ANDk-function in the number in the hand model. Our (n/k) bound for disjointness improves on an earlier (n/(k log k)) bound by Chakrabarti et al. (2003), who obtained an asymptotically tight lower bound for one-way protocols, but failed to do so for the general case. Our result eliminates both the gap between the upper and the lower bound for unrestricted protocols and the gap between the lower bounds for one-way protocols and unrestricted protocols.

Affiliated with

Also associated with

No associations

Rating

Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-19798