We prove a randomized communication-complexity lower bound for a composed OrderedSearch 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.