Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR17-010 | 28th January 2017 21:10

#### Raz-McKenzie simulation with the inner product gadget

Revision #1
Authors: Xiaodi Wu, Penghui Yao, Henry Yuen
Accepted on: 28th January 2017 21:10
Keywords:

Abstract:

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: \{0,1\}^n \to \{0,1\}$ with deterministic query complexity $D(f)$, we show that the deterministic communication complexity of the composed function $f \circ g_{IP}^n$ is $\Theta( D(f) \log n)$, where
$$f \circ g_{IP}^n (x,y) = f( g_{IP}(x^1,y^1),\ldots,g_{IP}(x^n,y^n))$$
where $x = (x^1,\ldots,x^n)$, $y = (y^1,\ldots,y^n)$ and each $x^i$ and $y^i$ are $O(\log n)$ bit strings. In [Raz, McKenzie FOCS 1997] and [Göös, et al. FOCS 2015], the simulation algorithm is implemented for functions composed with the Indexing gadget, where the size of the gadget is polynomial in the input length of the outer function $f$.

Changes to previous version:

Added a citation to an independent work of Chattopadhyay, et al. who also prove a simulation theorem using the Inner Product gadget.

### Paper:

TR17-010 | 18th January 2017 22:11

#### Raz-McKenzie simulation with the inner product gadget

TR17-010
Authors: Xiaodi Wu, Penghui Yao, Henry Yuen
Publication: 22nd January 2017 21:04
Keywords:

Abstract:

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: \{0,1\}^n \to \{0,1\}$ with deterministic query complexity $D(f)$, we show that the deterministic communication complexity of the composed function $f \circ g_{IP}^n$ is $\Theta( D(f) \log n)$, where
$$f \circ g_{IP}^n (x,y) = f( g_{IP}(x^1,y^1),\ldots,g_{IP}(x^n,y^n))$$
where $x = (x^1,\ldots,x^n)$, $y = (y^1,\ldots,y^n)$ and each $x^i$ and $y^i$ are $O(\log n)$ bit strings. In [Raz, McKenzie FOCS 1997] and [Göös, et al. FOCS 2015], the simulation algorithm is implemented for functions composed with the Indexing gadget, where the size of the gadget is polynomial in the input length of the outer function $f$.

ISSN 1433-8092 | Imprint