On the success probability of the two provers in one-round proof systems
Uriel Feige · 2002
The author addresses the problem of reducing the error probability of two-prover one-round proof systems, without increasing the number of provers or the number of rounds. An example, the noninteractive agreement protocol, where executing such a protocol twice in parallel does not decrease the error probability at all is constructed. Upper bounds on the error probability of specific classes of protocols are proved. As a corollary, it is shown that every NEXPTIME language has a one-round two-prover proof system with constant error probability.>