Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with ordered search:
TR17-014 | 23rd January 2017
Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

Composition and Simulation Theorems via Pseudo-random Properties

We prove a randomized communication-complexity lower bound for a composed OrderedSearch $\circ$ IP — by lifting the randomized query-complexity lower-bound of OrderedSearch to the communication-complexity setting. We do this by extending ideas from a paper of Raz and Wigderson. We think that the techniques we develop will be useful in ... more >>>

ISSN 1433-8092 | Imprint