Alternation in Interaction

Authors: Marcos Kiwi, Carsten Lund, Alex Russell, Daniel Spielman, and Ravi Sundaram.

Bibliographic Information: Computational Complexity, 9(3-4):202-246, 2000

Extended abstract appeared in Proceedings of the 9th Annual IEEE Conference on Structure in Complexity Theory, 1994, pp. 294-303.


We study competing-prover one-round interactive proof systems. We show that one-round proof systems in which the first prover is trying to convince a verifier to accept and the second prover is trying to make the verifier reject recognize languages in $\NEXPTIME$, and, with restrictions on communication and randomness, languages in $\NP$. We extended the restricted model to an alternating sequence of $k$ competing provers, which we show characterizes $\Sigma_{k-1}^{P}$. Alternating oracle proof systems are also examined.
To view the paper, click here.

To view a compressed version, click here.

Daniel A. Spielman
Last modified: Fri Aug 29 15:42:39 EDT 2003