The hardness of Median in the synchronized bit communication model

Details The hardness of Median in the synchronized bit communication model The hardness of Median in the synchronized bit communication model

2011-02-06

arxiv.org/abs/1102.1208v1

Computer Science

Computational Complexity

Scientific paper

The synchronized bit communication model, defined recently by Impagliazzo and Williams in \emph{Communication complexity with synchronized clocks}, CCC '10, is a communication model which allows the participants to share a common clock. The main open problem posed in this paper was the following: does the synchronized bit model allow a logarithmic speed-up for all functions over the standard deterministic model of communication? We resolve this question in the negative by showing that the Median function, whose communication complexity is $O(\log n)$, does not admit polytime synchronized bit protocol with communication complexity $O\left(\log^{1-\epsilon} n\right)$ for any $\epsilon > 0$. Our results follow by a new round-communication trade-off for the Median function in the standard model, which easily translates to its hardness in the synchronized bit model.

Affiliated with

Also associated with

No associations

Rating

The hardness of Median in the synchronized bit communication model 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 The hardness of Median in the synchronized bit communication model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The hardness of Median in the synchronized bit communication model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-680394