ECCC-Report TR17-010https://eccc.weizmann.ac.il/report/2017/010Comments and Revisions published for TR17-010en-usSat, 28 Jan 2017 21:10:09 +0200
Revision 1
| Raz-McKenzie simulation with the inner product gadget |
Henry Yuen,
Xiaodi Wu,
Penghui Yao
https://eccc.weizmann.ac.il/report/2017/010#revision1In 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$.Sat, 28 Jan 2017 21:10:09 +0200https://eccc.weizmann.ac.il/report/2017/010#revision1
Paper TR17-010
| Raz-McKenzie simulation with the inner product gadget |
Henry Yuen,
Xiaodi Wu,
Penghui Yao
https://eccc.weizmann.ac.il/report/2017/010In 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$.Sun, 22 Jan 2017 21:04:05 +0200https://eccc.weizmann.ac.il/report/2017/010