Consider $IP(f(x))$, in other words, the class of languages that admit a private coin protocol $(P, V)$ running in $f(x)$ rounds (often in terms of the size of $x$), satisfying standard constraints.

Does it matter who sends the first message?

  • 1
    $\begingroup$ In the one-round case this is the MA vs. AM question. In full-fledged IP where $f$ is a polynomial a protocol taking one fewer round seems more or less irrelevant. $\endgroup$ Oct 10, 2015 at 18:18
  • $\begingroup$ This seems similar to asking if there is a "rounds of communication hierarchy theorem"? E.g., if $IP(f(x)) \subsetneq IP(f(x)+1)$, then maybe/probably it does matter. $\endgroup$
    – usul
    Oct 10, 2015 at 18:23
  • $\begingroup$ @usul, yes, that's exactly the kind of thing I'm looking for - do such results exist? $\endgroup$
    – Phylliida
    Oct 11, 2015 at 1:49
  • $\begingroup$ @HuckBennett That is with public coins though, does having private coins instead make a difference? $\endgroup$
    – Phylliida
    Oct 11, 2015 at 2:40
  • $\begingroup$ By Goldwasser-Sipser (people.csail.mit.edu/madhu/ST07/scribe/lect15.pdf) using public vs. private coins doesn't change the number of rounds at all for constant round protocols, and increases protocols by at most 2 rounds in general. I don't remember how this distinctions comes in, so maybe someone who does can clarify. $\endgroup$ Oct 15, 2015 at 0:52


Your Answer

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

Browse other questions tagged or ask your own question.