Rectangle Size Bounds and Threshold Covers in Communication Complexity

Details Rectangle Size Bounds and Threshold Covers in Communication Complexity Rectangle Size Bounds and Threshold Covers in Communication Complexity

2002-08-05

arxiv.org/abs/cs/0208006v1

Computer Science

Computational Complexity

34 pages

Scientific paper

We investigate the power of the most important lower bound technique in randomized communication complexity, which is based on an evaluation of the maximal size of approximately monochromatic rectangles, minimized over all distributions on the inputs. While it is known that the 0-error version of this bound is polynomially tight for deterministic communication, nothing in this direction is known for constant error and randomized communication complexity. We first study a one-sided version of this bound and obtain that its value lies between the MA- and AM-complexities of the considered function. Hence the lower bound actually works for a (communication complexity) class between MA cap co-MA and AM cap co-AM. We also show that the MA-complexity of the disjointness problem is Omega(sqrt(n)). Following this we consider the conjecture that the lower bound method is polynomially tight for randomized communication complexity. First we disprove a distributional version of this conjecture. Then we give a combinatorial characterization of the value of the lower bound method, in which the optimization over all distributions is absent. This characterization is done by what we call a uniform threshold cover. We also study relaxations of this notion, namely approximate majority covers and majority covers, and compare these three notions in power, exhibiting exponential separations. Each of these covers captures a lower bound method previously used for randomized communication complexity.

Affiliated with

Also associated with

No associations

Rating

Rectangle Size Bounds and Threshold Covers in 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 Rectangle Size Bounds and Threshold Covers in Communication Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rectangle Size Bounds and Threshold Covers in Communication Complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-250964