I am currently organizing the literature of composition theorem, and I found the paper by https://www.research.cs.rutgers.edu/~troyjlee/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=, 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?


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.

[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.

  • $\begingroup$ 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? $\endgroup$ – exteral Dec 9 '20 at 14:35
  • $\begingroup$ 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 :) $\endgroup$ – Clement C. Dec 9 '20 at 18:46
  • $\begingroup$ 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. $\endgroup$ – exteral Dec 9 '20 at 18:59
  • $\begingroup$ 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") $\endgroup$ – Clement C. Dec 9 '20 at 21:10
  • $\begingroup$ I see. Thx Clement. Completely new to quantum area, might take some time to delve into it. $\endgroup$ – exteral Dec 9 '20 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.