The function $\mathrm{INDEX}:\{0,1\}^n\times\{1,\dots,n\}\to \{0,1\}$ is defined as

$$\mathrm{INDEX}(x,i)=x_i,$$ where $x=x_1\dots x_n$. I am looking for the randomized communication complexity of $\mathrm{INDEX}$ for an arbitrary number of rounds.

Somehow, I do not manage to find it in the literature.

The deterministic communication complexity is known to be $\Theta(\log n)$, while its one-way randomized communication complexity is $\Theta(n)$.

I guess the randomized communication complexity is still $\Theta(\log n)$, I was not able to find a lower bound.

Since this function its well-studied, it should be stated somewhere.

Thanks for your help.

  • $\begingroup$ There should be a simple information-theoretic argument. Discrepancy might also work. $\endgroup$ – Yuval Filmus Jan 24 '19 at 13:17
  • $\begingroup$ The result itself should follow from known lifting theorems, but that’s overkill. $\endgroup$ – Yuval Filmus Jan 24 '19 at 13:18
  • $\begingroup$ Average or worst case complexity? $\endgroup$ – orlp Jan 24 '19 at 15:41
  • $\begingroup$ Communication complexity is always worst case. $\endgroup$ – Yuval Filmus Jan 24 '19 at 17:38

It is known that the randomized communication complexity of inner product on $m$ bits is $\Omega(m)$. You can compute inner product using a protocol for the indexing function on $\{0,1\}^{2^m} \times [2^m]$ as follows: denoting Alice's input by $x \in \{0,1\}^m$ and Bob's by $y \in \{0,1\}^m$, Alice computes a new vector $X$ by $X_y = \mathsf{IP}(x,y)$, and the parties run the indexing protocol on the inputs $X$ and $y$. This gives an $\Omega(m) = \Omega(\log n)$ lower bound for indexing.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.