Revision #1 Authors: Xiaodi Wu, Penghui Yao, Henry Yuen

Accepted on: 28th January 2017 21:10

Downloads: 540

Keywords:

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

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

TR17-010 Authors: Xiaodi Wu, Penghui Yao, Henry Yuen

Publication: 22nd January 2017 21:04

Downloads: 601

Keywords:

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