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
scroll top