Complessità comunicativa randomizzata dell'indicizzazione

Question

La funzione $ mathrm {indice}: {0,1 }^n tempes {1, dots, n } to {0,1 } $ è definito come

$$ mathrm {indice} (x, i) = x_i, $$dove $ x = x_1 dots x_n $. Sto cercando la complessità comunicativa randomizzata di $ mathrm {indice} $ Per un numero arbitrario di round.

In qualche modo, non riesco a trovarlo in letteratura.

La complessità della comunicazione deterministica è nota per essere $ Theta ( log n) $, mentre la sua complessità comunicativa randomizzata a senso unico è $ Theta (n) $.

Immagino che la complessità della comunicazione randomizzata sia ancora $ Theta ( log n) $, Non sono stato in grado di trovare un limite inferiore.

Dal momento che questa funzione è ben studiata, dovrebbe essere dichiarata da qualche parte.

Grazie per l'aiuto.