Randomized communication complexity of indexing
Pergunta
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.
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange