Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR17-014 | 23rd January 2017 15:55

#### Composition and Simulation Theorems via Pseudo-random Properties

TR17-014
Publication: 27th January 2017 23:28
Keywords:

Abstract:

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