Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR17-014 | 23rd January 2017 15:55

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 proving a randomized simulation theorem.

We also generalize the deterministic simulation theorem of Raz and McKenzie, to any inner-function which satisfies certain hitting property. We prove that IP satisfies this property, and as a corollary we obtain deterministic simulation theorem for an inner-function gadget with logarithmic block-size with respect to the arity of the outer function. This answers an open question posed by G\"{o}\"{o}s, Pitassi and Watson. Our result also implies the previous results for the Indexing inner-function.

ISSN 1433-8092 | Imprint