Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Raz-McKenzie simulation with the inner product gadget

RSS-Feed




Revision #1
Authors: Xiaodi Wu, Penghui Yao, Henry Yuen
Accepted on: 28th January 2017 21:10
Downloads: 1307
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
Downloads: 1514
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