Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR17-152 | 9th October 2017 15:14

One-way Communication and Non-adaptive Decision Tree

TR17-152
Authors: Swagato Sanyal
Publication: 11th October 2017 19:20
Keywords:

Abstract:

Let $f$ be a Boolean function on $n$-bits, and $\mathsf{IP}$ the inner-product function on $2b$ bits. Let $f^{\mathsf{IP}}:=f \circ \mathsf{IP}^n$ be the two party function obtained by composing $f$ with $\mathsf{IP}$. In this work we bound the one-way communication complexity of $f^{\IP}$ in terms of the non-adaptive query complexity of $f$, from below. Similar results are known for general communication protocols and adaptive decision trees, when the arity of the inner function (inner-product in our case) is at least logarithmic in $n$. We prove analogous results for one-way communication as long as $b$ is a large enough constant. Let $\sR_{\cc, \epsilon}^{\rightarrow}(\cdot)$ and $\sD_{\cc}^\rightarrow(\cdot)$ denote the randomized $\epsilon$-error and deterministic one-way communication complexity respectively. Let $\sD_{\dt}^\rightarrow(\cdot)$ denote the deterministic non-adaptive query complexity. Let $\rH_{\bin}(\cdot)$ denote the binary entropy function. We prove that
\begin{itemize}
\item If $f$ is a \emph{total} Boolean function and $b \geq 2$, then $\sR^{\rightarrow}_{\cc, \epsilon}(f^{\mathsf{IP}}) \geq (1-\rH_{\bin}(\epsilon))n(b-1)$.
\item If $f$ is a partial Boolean function and $b \geq 4$, then $\sD_{\cc}^\rightarrow(f^{\mathsf{IP}})=\Omega(b \cdot \sD_{\dt}^\rightarrow(f))$.
\end{itemize}

ISSN 1433-8092 | Imprint