Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SIMULATION THEOEREMS:
Reports tagged with simulation theoerems:
TR17-010 | 18th January 2017
Xiaodi Wu, Penghui Yao, Henry Yuen

Revisions: 1

In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions $f$ composed with the Inner Product gadget $g_{IP}(x,y) = \sum_i x_iy_i \mathrm{mod} \, 2$ of logarithmic size. In other words, given a function $f: ... more >>> 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