|
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 \Gammak(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: f0; 1g l, |
