Randomness in interactive proofs

Abstract

This paper initiates a study of the quantitative aspects of randomness in interactive proofs. Our main result, which applies to the equivalent form of IP known as Arthur-Merlin (AM) games, is a randomness-efficient technique for decreasing the error probability. Given an AM proof system for L which achieves error probability 1/3 at the cost of Arthur sending l(n) random bits per round, and given a polynomial k=k(n), we show how to construct an AM proof system for L which, in the same number of rounds as the original proof system, achieves error 2-k(n) at the cost of Arthur sending only O(l+k) random bits per round. Underlying the transformation is a novel sampling method for approximating the average value of an arbitrary function f:{0,1}l → [0,1]. The method evaluates the function on O(∈-2 log γ-1) sample points generated using only O(l + log γ-1) coin tosses to get an estimate which with probability at least 1-δ is within ∈ of the average value of the function. © 1993 Birkhäuser Verlag.