All reports by Author Naresh Goud:

__
TR17-054
| 22nd March 2017
__

Anurag Anshu, Naresh Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay#### Lifting randomized query complexity to randomized communication complexity

Revisions: 4

Anurag Anshu, Naresh Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay

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 $x$th bit ... more >>>