We show that for any (partial) query function f:\{0,1\}^n\rightarrow \{0,1\}, the randomized communication complexity of f composed with \mathrm{Index}^n_m (with m= \poly(n)) is at least the randomized query complexity of f times \log n. Here \mathrm{Index}_m : [m] \times \{0,1\}^m \rightarrow \{0,1\} is defined as \mathrm{Index}_m(x,y)= y_x (the xth bit ... more >>>