All Questions
Tagged with communication-complexity randomized
1 question
1
vote
1
answer
191
views
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 $\...
- 994