ECCC-Report TR21-065https://eccc.weizmann.ac.il/report/2021/065Comments and Revisions published for TR21-065en-usMon, 10 May 2021 20:00:27 +0300
Revision 1
| One-way communication complexity and non-adaptive decision trees |
Nikhil Mande,
Swagato Sanyal
https://eccc.weizmann.ac.il/report/2021/065#revision1We 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 [STOC'00].
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 [arXiv'09] 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.
For the second bullet, we first observe a connection between the one-way communication complexity of $f$ and the M\"obius sparsity of $f$, and then use a known lower bound on the M\"obius sparsity of symmetric functions. An upper bound on the non-adaptive AND decision tree complexity of symmetric functions follows implicitly from prior work on combinatorial group testing; for the sake of completeness, we include a proof of this result.Mon, 10 May 2021 20:00:27 +0300https://eccc.weizmann.ac.il/report/2021/065#revision1
Paper TR21-065
| One-way communication complexity and non-adaptive decision trees |
Nikhil Mande,
Swagato Sanyal
https://eccc.weizmann.ac.il/report/2021/065We 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 [STOC'00].
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 [arXiv'09] 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.
For the second bullet, we first observe a connection between the one-way communication complexity of $f$ and the M\"obius sparsity of $f$, and then use a known lower bound on the M\"obius sparsity of symmetric functions. An upper bound on the non-adaptive AND decision tree complexity of symmetric functions follows implicitly from prior work on combinatorial group testing; for the sake of completeness, we include a proof of this result.Wed, 05 May 2021 16:16:19 +0300https://eccc.weizmann.ac.il/report/2021/065