ISSN:
1420-8954
Keywords:
Interactive proof systems
;
Arthur-Merlin games
;
randomness
;
sampling methods
;
expander graphs
;
pairwise independence
;
68Q99
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
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 forL which achieves error probability 1/3 at the cost of Arthur sendingl(n) random bits per round, and given a polynomialk=k(n), we show how to construct an AM proof system forL which, in the same number of rounds as the original proof system, achieves error 2 −k(n) at the cost of Arthur sending onlyO(l+k) random bits per round. Underlying the transformation is a novel sampling method for approximating the average value of an arbitrary functionf:{0,1} l → [0,1]. The method evaluates the function onO(∈−2 log γ−1) sample points generated using onlyO(l + log γ−1) coin tosses to get an estimate which with probability at least 1-δ is within ∈ of the average value of the function.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01275487
Permalink
