A Strong Direct Product Theorem for Disjointness

Details A Strong Direct Product Theorem for Disjointness A Strong Direct Product Theorem for Disjointness

2009-08-20

arxiv.org/abs/0908.2940v3

Computer Science

Computational Complexity

Scientific paper

A strong direct product theorem states that if we want to compute $k$ independent instances of a function, using less than $k$ times the resources needed for one instance, then the overall success probability will be exponentially small in $k$. We establish such a theorem for the randomized communication complexity of the Disjointness problem, i.e., with communication $const\cdot kn$ the success probability of solving $k$ instances of size $n$ can only be exponentially small in $k$. We show that this bound even holds for $AM$ communication protocols with limited ambiguity. This also implies a new lower bound for Disjointness in a restricted 3-player NOF protocol, and optimal communication-space tradeoffs for Boolean matrix product. Our main result follows from a solution to the dual of a linear programming problem, whose feasibility comes from a so-called Intersection Sampling Lemma that generalizes a result by Razborov.

Affiliated with

Also associated with

No associations

Rating

A Strong Direct Product Theorem for Disjointness 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 A Strong Direct Product Theorem for Disjointness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Strong Direct Product Theorem for Disjointness will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-526881