In the web draft of Arora and Barak, "Computational Complexity: A Modern Approach", the way I understand their definition of a round of interaction is that it consists of either the verifier or the prover sending a message. In other sources on the matter, it seems to me that a round consists of both the verifier and the prover sending a message. Could someone clarify which of the definitions is the one that is usually used?
1
-
$\begingroup$ @YuvalFilmus Thanks, I assumed that either there's a commonly used definition, or - as is often times the case - that different, but somewhat equivalent definitions are in use. If you care for the points, please post your comment as an answer. $\endgroup$ – G. Bach Jul 27 '13 at 15:44
Add a comment
|
$\begingroup$
$\endgroup$
It could be that both definitions are used by different authors. Whenever you use the concept of rounds, make sure to tell the reader what you mean by a round. In any case, the two concepts differ by a factor of $2$.