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?

  • $\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, 2013 at 15:44

1 Answer 1


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


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.