From ACM Distinguished Dissertation

The Power of Interaction

By Carsten Lund




The Power of Interaction presents a new algebraic technique for constructing interactive proof systems and demonstrates the immense power of randomization and interaction in proving statements efficiently. Lund shows that two provers can interact with a randomized verifier to provide proofs that are exponentially more efficient than traditional proofs, and that one prover can interact with an efficient randomized verifier to prove statements that have no known efficient traditional proofs.


Out of Print ISBN: 9780262121705 141 pp. | 7.25 in x 9.25 in