Randomness in interactive proofs
Randomness in interactive proofs
复制标题
交互式证明中的随机性
DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
S. Goldwasser
中科院分区：
文献类型：
--
作者：
M. Bellare;Oded Goldreich;S. Goldwasser
本文提出了一种研究的定量方面的随机性在互动的证明。我们的主要结果，这适用于等价形式的IP称为亚瑟-梅林（AM）游戏，是一个随机有效的技术，降低错误概率。给定一个L的AM证明系统，它以每轮亚瑟发送l（n）个随机比特为代价实现错误概率1/3，并给定一个多项式k =k（n），我们展示了如何构造一个L的AM证明系统，它在与原始证明系统相同的轮数中，以亚瑟只发送O（l+k）为代价实现错误2−k（n）该变换的基础是一种用于逼近任意函数f：{0，1}l → [0，1]的平均值的新颖采样方法。该方法对仅使用O（l + log γ-1）次硬币投掷生成的O（∈-2 log γ-1）个样本点上的函数进行评估，以获得至少1-δ在函数平均值∈内的概率的估计。
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.