1
$\begingroup$

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=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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
5
  • $\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, 2020 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, 2020 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, 2020 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, 2020 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, 2020 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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