<p>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.</p>

<p>Does it matter who sends the first message?</p>

CC BY-SA 3.0
2015-10-10T18:18:14.203Z
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.
Huck Bennett
CC BY-SA 3.0
2015-10-10T18:23:05.417Z
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.
usul
CC BY-SA 3.0
2015-10-11T01:49:49.953Z
@usul, yes, that's exactly the kind of thing I'm looking for - do such results exist?
Phylliida
CC BY-SA 3.0
2015-10-11T02:40:49.797Z
@HuckBennett That is with public coins though, does having private coins instead make a difference?
Phylliida
CC BY-SA 3.0
2015-10-15T00:52:01.733Z
By Goldwasser-Sipser (http://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.
Huck Bennett
<complexity-classes><interactive-proofs>
Does it matter who begins communication in $IP(f(x))$?
Phylliida
# Does it matter who begins communication in $IP(f(x))$?

(Asked by: username_0 on 2015-10-08)

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?

**Tags:** complexity-classes, interactive-proofs

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_0**: @username_2, yes, that's exactly the kind of thing I'm looking for - do such results exist?  
> **username_0**: @HuckBennett That is with public coins though, does having private coins instead make a difference?  
> **username_1**: By Goldwasser-Sipser (http://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.  

---

## 0 answers

