<p>My understanding is that it's not following from [Nisan94], but from [BCW98] (note that there are two citations provided from Theorem 5), specifically their Theorem 2.1. while phrased for quantum, this generalizes to classical models as well.</p>
<p>See Theorem 69 of Troy Lee and Adi Shraibman's survey [LS09], available, e.g., <a href="https://www.research.cs.rutgers.edu/%7Etroyjlee/survey_plain.pdf" rel="nofollow noreferrer">at this address</a>.</p>
<hr />
<p>[BCW98] Buhrman, Harry; Cleve, Richard; Wigderson, Avi. <em>Quantum vs. classical communication and computation.</em> STOC '98 (Dallas, TX), 63--68, ACM, New York, 1999. Available at <a href="https://arxiv.org/abs/quant-ph/9802040" rel="nofollow noreferrer">https://arxiv.org/abs/quant-ph/9802040</a></p>
<p>[LS09] Troy Lee and Adi Shraibman, <em>Lower Bounds in Communication Complexity</em>, Foundations and Trends® in Theoretical Computer Science: Vol. 3: No. 4, pp 263-399. 2009. <a href="http://dx.doi.org/10.1561/0400000040" rel="nofollow noreferrer">http://dx.doi.org/10.1561/0400000040</a></p>
<p>[Nisan94] Nisan, N. The communication complexity of threshold gates. Combinatorics, Paul Erdős is eighty, Vol. 1, 301--315, Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 1993.</p>

CC BY-SA 4.0
2020-12-09T14:35:40.440Z
I see, didn't know quantum cc can generalize to classical cc. Is it for all the results that quantum cc gets or only a part of them?
exteral
CC BY-SA 4.0
2020-12-09T18:46:42.260Z
It's not a general fact, just particular to this specific one (basically, the idea of the proof carries over). Again, based on my understanding :)
Clement C.
CC BY-SA 4.0
2020-12-09T18:59:01.560Z
On the other hand, in the theorem 5 of [LZ10], it doesn't really seem clear to me which one is related to [Nis94] though.
exteral
CC BY-SA 4.0
2020-12-09T21:10:50.733Z
It may just be the case that some ideas used in the [CLW98] simulation result are implicit in [Nisan94] (this is what the discussion in Lee's paper hints at: "A fundamental idea going back to Nisan")
Clement C.
CC BY-SA 4.0
2020-12-09T22:44:54.923Z
I see. Thx Clement. Completely new to quantum area, might take some time to delve into it.
exteral
CC BY-SA 4.0
2020-12-09T08:43:38.803Z
2020-12-09T08:43:38.803Z
Clement C.
<p>I am currently organizing the literature of composition theorem, and I found the paper by <a href="https://www.research.cs.rutgers.edu/%7Etroyjlee/Composition.pdf" rel="nofollow noreferrer">https://www.research.cs.rutgers.edu/~troyjlee/Composition.pdf</a>, in their theorem 5, I find
<span class="math-container">$$ R_{1/4} (f \circ g^{n}) = \mathcal{O}(RT_{1/4}(f)R_{1/4}(g)\log RT_{1/4}(f)) $$</span> coming from Nisan's paper <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.6891&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.6891&amp;rep=rep1&amp;type=pdf</a>, where <span class="math-container">$RT(f)$</span> is denoted as query complexity and <span class="math-container">$R(f)$</span> is the randomized communication complexity.</p>
<p>However, I am not sure I notice such a conclusion has ever been drawn in Nisan's paper. The closest claim I suppose is the lemma 3, where Nisan claims that</p>
<blockquote>
<p>Let <span class="math-container">$G$</span> be a family of functions. If a function <span class="math-container">$f$</span> can be computed by a circuit consisting of <span class="math-container">$s$</span> gates from <span class="math-container">$G$</span> then, for all <span class="math-container">$k$</span>, <span class="math-container">$R^{k}(f) \leq s \cdot R^{k}_{1/3s}(G)$</span>.</p>
</blockquote>
<p>My question is : is it the lemma leading to the theorem 5 of the first paper, and how? Or am I missing something here?</p>

<circuit-complexity><communication-complexity><query-complexity>
Composition theorem for randomized communication complexity
exteral
# Composition theorem for randomized communication complexity

(Asked by: username_0 on 2020-12-09)

I am currently organizing the literature of composition theorem, and I found the paper by [https://www.research.cs.rutgers.edu/~troyjlee/Composition.pdf](https://www.research.cs.rutgers.edu/%7Etroyjlee/Composition.pdf), in their theorem 5, I find
$$ R\_{1/4} (f \circ g^{n}) = \mathcal{O}(RT\_{1/4}(f)R\_{1/4}(g)\log RT\_{1/4}(f)) $$ coming from Nisan's paper <http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.6891&rep=rep1&type=pdf>, where $RT(f)$ is denoted as query complexity and $R(f)$ is the randomized communication complexity.

However, I am not sure I notice such a conclusion has ever been drawn in Nisan's paper. The closest claim I suppose is the lemma 3, where Nisan claims that

> Let $G$ be a family of functions. If a function $f$ can be computed by a circuit consisting of $s$ gates from $G$ then, for all $k$, $R^{k}(f) \leq s \cdot R^{k}\_{1/3s}(G)$.

My question is : is it the lemma leading to the theorem 5 of the first paper, and how? Or am I missing something here?

**Tags:** circuit-complexity, communication-complexity, query-complexity


---

## 1 answers

### Answer by username_1 on 2020-12-09. Score: 1 | Accepted answer

My understanding is that it's not following from [Nisan94], but from [BCW98] (note that there are two citations provided from Theorem 5), specifically their Theorem 2.1. while phrased for quantum, this generalizes to classical models as well.

See Theorem 69 of Troy Lee and Adi Shraibman's survey [LS09], available, e.g., [at this address](https://www.research.cs.rutgers.edu/%7Etroyjlee/survey_plain.pdf).

---

[BCW98] Buhrman, Harry; Cleve, Richard; Wigderson, Avi. *Quantum vs. classical communication and computation.* STOC '98 (Dallas, TX), 63--68, ACM, New York, 1999. Available at <https://arxiv.org/abs/quant-ph/9802040>

[LS09] Troy Lee and Adi Shraibman, *Lower Bounds in Communication Complexity*, Foundations and Trends® in Theoretical Computer Science: Vol. 3: No. 4, pp 263-399. 2009. <http://dx.doi.org/10.1561/0400000040>

[Nisan94] Nisan, N. The communication complexity of threshold gates. Combinatorics, Paul Erdős is eighty, Vol. 1, 301--315, Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 1993.

> **Comments:**
> **username_0**: I see, didn't know quantum cc can generalize to classical cc. Is it for all the results that quantum cc gets or only a part of them?  
> **username_1**: It's not a general fact, just particular to this specific one (basically, the idea of the proof carries over). Again, based on my understanding :)  
> **username_0**: On the other hand, in the theorem 5 of [LZ10], it doesn't really seem clear to me which one is related to [Nis94] though.  
> **username_1**: It may just be the case that some ideas used in the [CLW98] simulation result are implicit in [Nisan94] (this is what the discussion in Lee's paper hints at: "A fundamental idea going back to Nisan")  
> **username_0**: I see. Thx Clement. Completely new to quantum area, might take some time to delve into it.  

---

