Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > NARESH GOUD:
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

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




ISSN 1433-8092 | Imprint