Error Reduction in Probabilistic Proof Systems
Dr Oleg Verbitsky, Mathematical Institute, Prague (on leave from Lviv University, Ukraine)

Abstract: We survey the concept of an interactive proof system. This is a probabilistic model, where several powerful provers try to convince a polynomial-time limited verifier that a given statement is true. A bounded error probability is permissible. During last years the study of interactive proofs has developed into a respectable area in complexity theory, with numerous striking applications in optimization (hardness of approximation results), cryptography (zero knowledge proofs), and structural complexity (new characterizations of the complexity classes NP, PSPACE etc.)

We shall be concerned with a question of how to attain small error when designing a proof system. The most natural attempt to do this is straight parallel repetition of a proof. The analysis of how efficient this way is proves to be a subtle issue. We express the error probability under parallel repetition in combinatorial terms, involving means of extremal graph theory and Ramsey theory. This allows us to estimate the error probability from above. Somewhat surprisingly, we show that the same approach provides also lower bounds matching the best known upper bounds.

This seminar was held at the Department of Computer Science, Royal Holloway, University of London on 21 September 1998.

back