patternMinor
Number of rounds in interactive proofs - Arora & Barak
Viewed 0 times
aroranumberinteractiveroundsbarakproofs
Problem
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?
Solution
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$.
Context
StackExchange Computer Science Q#13452, answer score: 5
Revisions (0)
No revisions yet.