Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR17-152 | 9th October 2017 15:14

One-way Communication and Non-adaptive Decision Tree


Authors: Swagato Sanyal
Publication: 11th October 2017 19:20
Downloads: 1091


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


Comment #1 to TR17-152 | 12th December 2017 12:43

One-way quantum communication complexity with inner product gadget

Comment #1
Authors: Srijita Kundu
Accepted on: 12th December 2017 12:43
Downloads: 1263


This note is prepared based on the article titled ``One-way Communication and Non-adaptive Decision Tree" (TR17-152) by Swagato Sanyal. We show that the technique developed in the aforementioned paper to lower bound one-way randomized communication complexity can be be extended to prove one-way quantum communication complexity with shared entanglement of any total query function $f : \{0,1\}^n \to \{0,1\}$ that depends on all its input bits, composed with the inner product gadget $\mathrm{IP}_m$ of size $m \geq 2$, is $\Omega(nm)$.

ISSN 1433-8092 | Imprint