# Randomized communication complexity of indexing

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.

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

## 1 Answer

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.