Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOne-way communication complexity and non-adaptive decision trees
146
0
0.0
(
0
)
Added by
Nikhil Mande
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs. Let $IP$ denote Inner Product on $2b$ bits. 1) If $f$ is a total Boolean function that depends on all of its inputs, the bounded-error one-way quantum communication complexity of $f circ IP$ equals $Omega(n(b-1))$. 2) If $f$ is a partial Boolean function, the deterministic one-way communication complexity of $f circ IP$ is at least $Omega(b cdot D_{dt}^{rightarrow}(f))$, where $D_{dt}^{rightarrow}(f)$ denotes the non-adaptive decision tree complexity of $f$. For our quantum lower bound, we show a lower bound on the VC-dimension of $f circ IP$, and then appeal to a result of Klauck [STOC00]. Our deterministic lower bound relies on a combinatorial result due to Frankl and Tokushige [Comb.99]. It is known due to a result of Montanaro and Osborne [arXiv09] that the deterministic one-way communication complexity of $f circ XOR_2$ equals the non-adaptive parity decision tree complexity of $f$. In contrast, we show the following with the gadget $AND_2$. 1) There exists a function for which even the randomized non-adaptive AND decision tree complexity of $f$ is exponentially large in the deterministic one-way communication complexity of $f circ AND_2$. 2) For symmetric functions $f$, the non-adaptive AND decision tree complexity of $f$ is at most quadratic in the (even two-way) communication complexity of $f circ AND_2$. In view of the first point, a lower bound on non-adaptive AND decision tree complexity of $f$ does not lift to a lower bound on one-way communication complexity of $f circ AND_2$. The proof of the first point above uses the well-studied Odd-Max-Bit function.
rate research
Read More
In this note, we study the relation between the parity decision tree complexity of a boolean function $f$, denoted by $mathrm{D}_{oplus}(f)$, and the $k$-party number-in-hand multiparty communication complexity of the XOR functions $F(x_1,ldots, x_k)= f(x_1opluscdotsoplus x_k)$, denoted by $mathrm{CC}^{(k)}(F)$. It is known that $mathrm{CC}^{(k)}(F)leq kcdotmathrm{D}_{oplus}(f)$ because the players can simulate the parity decision tree that computes $f$. In this note, we show that [mathrm{D}_{oplus}(f)leq Obig(mathrm{CC}^{(4)}(F)^5big).] Our main tool is a recent result from additive combinatorics due to Sanders. As $mathrm{CC}^{(k)}(F)$ is non-decreasing as $k$ grows, the parity decision tree complexity of $f$ and the communication complexity of the corresponding $k$-argument XOR functions are polynomially equivalent whenever $kgeq 4$. Remark: After the first version of this paper was finished, we discovered that Hatami and Lovett had already discovered the same result a few years ago, without writing it up.
Let $f: X times Y rightarrow {0,1,bot }$ be a partial function and $mu$ be a distribution with support contained in $f^{-1}(0) cup f^{-1}(1)$. Let $mathsf{D}^{1,mu}_epsilon(f)$ be the classical one-way communication complexity of $f$ with average error under $mu$ at most $epsilon$, $mathsf{Q}^{1,mu}_epsilon(f)$ be the quantum one-way communication complexity of $f$ with average error under $mu$ at most $epsilon$ and $mathsf{Q}^{1,mu, *}_epsilon(f)$ be the entanglement assisted one-way communication complexity of $f$ with average error under $mu$ at most $epsilon$. We show: 1. If $mu$ is a product distribution, then $forall epsilon, eta > 0$, $$mathsf{D}^{1,mu}_{2epsilon + eta}(f) leq mathsf{Q}^{1,mu, *}_{epsilon}(f) /eta+Obigl(log(mathsf{Q}^{1,mu, *}_{epsilon}(f))/etabigr).$$ 2. If $mu$ is a non-product distribution, then $forall epsilon, eta > 0$ such that $epsilon/eta + eta < 0.5$, $$mathsf{D}^{1,mu}_{3eta}(f) = O(mathsf{Q}^{1,mu}_{{epsilon}}(f) cdot mathsf{CS}(f)/eta^4)enspace,$$ where [mathsf{CS}(f) = max_{y} min_{zin{0,1}} { vert {x~|~f(x,y)=z} vert} enspace.]
We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation $fsubseteqmathcal{X}timesmathcal{Y}timesmathcal{Z}$. For any $varepsilon, zeta > 0$ and any $kgeq1$, we show that [ mathrm{Q}^1_{1-(1-varepsilon)^{Omega(zeta^6k/log|mathcal{Z}|)}}(f^k) = Omegaleft(kleft(zeta^5cdotmathrm{Q}^1_{varepsilon + 12zeta}(f) - loglog(1/zeta)right)right),] where $mathrm{Q}^1_{varepsilon}(f)$ represents the one-way entanglement-assisted quantum communication complexity of $f$ with worst-case error $varepsilon$ and $f^k$ denotes $k$ parallel instances of $f$. As far as we are aware, this is the first direct product theorem for quantum communication. Our techniques are inspired by the parallel repetition theorems for the entangled value of two-player non-local games, under product distributions due to Jain, Pereszl{e}nyi and Yao, and under anchored distributions due to Bavarian, Vidick and Yuen, as well as message-compression for quantum protocols due to Jain, Radhakrishnan and Sen. Our techniques also work for entangled non-local games which have input distributions anchored on any one side. In particular, we show that for any game $G = (q, mathcal{X}timesmathcal{Y}, mathcal{A}timesmathcal{B}, mathsf{V})$ where $q$ is a distribution on $mathcal{X}timesmathcal{Y}$ anchored on any one side with anchoring probability $zeta$, then [ omega^*(G^k) = left(1 - (1-omega^*(G))^5right)^{Omegaleft(frac{zeta^2 k}{log(|mathcal{A}|cdot|mathcal{B}|)}right)}] where $omega^*(G)$ represents the entangled value of the game $G$. This is a generalization of the result of Bavarian, Vidick and Yuen, who proved a parallel repetition theorem for games anchored on both sides, and potentially a simplification of their proof.
We study the communication complexity of computing functions $F:{0,1}^ntimes {0,1}^n rightarrow {0,1}$ in the memoryless communication model. Here, Alice is given $xin {0,1}^n$, Bob is given $yin {0,1}^n$ and their goal is to compute F(x,y) subject to the following constraint: at every round, Alice receives a message from Bob and her reply to Bob solely depends on the message received and her input x; the same applies to Bob. The cost of computing F in this model is the maximum number of bits exchanged in any round between Alice and Bob (on the worst case input x,y). In this paper, we also consider variants of our memoryless model wherein one party is allowed to have memory, the parties are allowed to communicate quantum bits, only one player is allowed to send messages. We show that our memoryless communication model capture the garden-hose model of computation by Buhrman et al. (ITCS13), space bounded communication complexity by Brody et al. (ITCS13) and the overlay communication complexity by Papakonstantinou et al. (CCC14). Thus the memoryless communication complexity model provides a unified framework to study space-bounded communication models. We establish the following: (1) We show that the memoryless communication complexity of F equals the logarithm of the size of the smallest bipartite branching program computing F (up to a factor 2); (2) We show that memoryless communication complexity equals garden-hose complexity; (3) We exhibit various exponential separations between these memoryless communication models. We end with an intriguing open question: can we find an explicit function F and universal constant c>1 for which the memoryless communication complexity is at least $c log n$? Note that $cgeq 2+varepsilon$ would imply a $Omega(n^{2+varepsilon})$ lower bound for general formula size, improving upon the best lower bound by Nev{c}iporuk in 1966.
We prove that for every parity decision tree of depth $d$ on $n$ variables, the sum of absolute values of Fourier coefficients at level $ell$ is at most $d^{ell/2} cdot O(ell cdot log(n))^ell$. Our result is nearly tight for small values of $ell$ and extends a previous Fourier bound for standard decision trees by Sherstov, Storozhenko, and Wu (STOC, 2021). As an application of our Fourier bounds, using the results of Bansal and Sinha (STOC, 2021), we show that the $k$-fold Forrelation problem has (randomized) parity decision tree complexity $tilde{Omega}left(n^{1-1/k}right)$, while having quantum query complexity $lceil k/2rceil$. Our proof follows a random-walk approach, analyzing the contribution of a random path in the decision tree to the level-$ell$ Fourier expression. To carry the argument, we apply a careful cleanup procedure to the parity decision tree, ensuring that the value of the random walk is bounded with high probability. We observe that step sizes for the level-$ell$ walks can be computed by the intermediate values of level $le ell-1$ walks, which calls for an inductive argument. Our approach differs from previous proofs of Tal (FOCS, 2020) and Sherstov, Storozhenko, and Wu (STOC, 2021) that relied on decompositions of the tree. In particular, for the special case of standard decision trees we view our proof as slightly simpler and more intuitive. In addition, we prove a similar bound for noisy decision trees of cost at most $d$ -- a model that was recently introduced by Ben-David and Blais (FOCS, 2020).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
