Strong direct product conjecture holds for all relations in public coin randomized one-way communication complexity

Details Strong direct product conjecture holds for all relations in public coin randomized one-way communication complexity Strong direct product conjecture holds for all relations in public coin randomized one-way communication complexity

2010-10-04

arxiv.org/abs/1010.0522v2

Computer Science

Computational Complexity

ver 2. 11 pages, proofs simplified

Scientific paper

Let f subset of X x Y x Z be a relation. Let the public coin one-way communication complexity of f, with worst case error 1/3, be denoted R^{1,pub}_{1/3}(f). We show that if for computing f^k (k independent copies of f), o(k R^{1,pub}_{1/3}(f)) communication is provided, then the success is exponentially small in k. This settles the strong direct product conjecture for all relations in public coin one-way communication complexity. We show a new tight characterization of public coin one-way communication complexity which strengthens on the tight characterization shown in [J., Klauck, Nayak 08]. We use the new characterization to show our direct product result and this may also be of independent interest.

Affiliated with

Also associated with

No associations

Rating

Strong direct product conjecture holds for all relations in public coin randomized one-way communication complexity 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 Strong direct product conjecture holds for all relations in public coin randomized one-way communication complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strong direct product conjecture holds for all relations in public coin randomized one-way communication complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-274216