Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

Raz-McKenzie simulation with the inner product gadget

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 >>>


TR18-175 | 23rd October 2018
Bruno Loff, Sagnik Mukhopadhyay

Lifting Theorems for Equality

Revisions: 2

We show a deterministic simulation (or lifting) theorem for composed problems $f \circ EQ_n$ where the inner function (the gadget) is Equality on $n$ bits. When $f$ is a total function on $p$ bits, it is easy to show via a rank argument that the communication complexity of $f\circ EQ_n$ ... more >>>


TR19-103 | 7th August 2019
Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi

Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Lifting theorems are theorems that relate the query complexity of a function $f:\left\{ 0,1 \right\}^n\to \left\{ 0,1 \right\}$ to the communication complexity of the composed function $f\circ g^n$, for some “gadget” $g:\left\{ 0,1 \right\}^b\times \left\{ 0,1 \right\}^b\to \left\{ 0,1 \right\}$. Such theorems allow transferring lower bounds from query complexity to ... more >>>




ISSN 1433-8092 | Imprint