HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Number of rounds in interactive proofs - Arora & Barak

Submitted by: @import:stackexchange-cs··
0
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.