Two Sides of the Coin Problem
Two Sides of the Coin Problem
复制标题
硬币问题的两个面
DOI：
10.4230/lipics.approx-random.2014.618
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
R. Raz
中科院分区：
文献类型：
--
作者：
Gil Cohen;Anat Ganor;R. Raz
在硬币问题中，给定一枚硬币的\(n\)次独立抛掷，该硬币偏向正面或反面的偏差\(b>0\)。目标是高置信度地确定硬币偏向哪一面。解决硬币问题的一个最优策略是对\(n\)个样本应用多数函数。只要对于某个常数\(c\)，\(b > c(1/\sqrt{n})\)，这个简单策略就有效。然而，对于一些自然的计算模型，例如有界宽度的一次读取分支程序和\(AC^0\)电路，计算多数是一项不可能的任务。
布罗迪和韦尔宾证明，对于长度为\(n\)、宽度为\(w\)的一次读取分支程序，当\(b < O(1/(\log n)^w)\)时无法解决硬币问题。斯坦伯格将这个结果收紧到\(O(1/(\log n)^{w - 2})\)。\(AC^0\)电路模型中的硬币问题首先由沙尔蒂尔和维奥拉研究，后来由 Aaronson研究，他证明对于深度为\(d\)、规模为\(s\)的布尔电路，当\(b < O(1/(\log s)^{d + 2})\)时无法解决硬币问题。
这项工作有两个贡献：
1. 我们强化了斯坦伯格的结果，并表明任何偏差\(b < O(1/(\log n)^{w - 2})\)的桑塔 - 瓦齐拉尼源都能欺骗长度为\(n\)、宽度为\(w\)的一次读取分支程序。换句话说，在一次读取分支程序模型中，假设偏差较小，硬币问题中的强独立性假设是完全多余的。也就是说，对于更广泛的一类源，完全相同的结果成立。
2. 我们收紧了Aaronson的结果，并表明对于深度为\(d\)、规模为\(s\)的布尔电路，当\(b < O(1/(\log s)^{d - 1})\)时无法解决硬币问题。此外，我们的证明技术不同，并且我们认为它更简单、更自然。
In the coin problem, one is given n independent flips of a coin that has bias b > 0 towards either Head or Tail. The goal is to decide which side the coin is biased towards, with high confidence. An optimal strategy for solving the coin problem is to apply the majority function on the n samples. This simple strategy works as long as b > c(1/sqrt n) for some constant c. However, computing majority is an impossible task for several natural computational models, such as bounded width read once branching programs and AC^0 circuits.
Brody and Verbin proved that a length n, width w read once branching program cannot solve the coin problem for b < O(1/(log n)^w). This result was tightened by Steinberger to O(1/(log n)^(w-2)). The coin problem in the model of AC^0 circuits was first studied by Shaltiel and Viola, and later by Aaronson who proved that a depth d size s Boolean circuit cannot solve the coin problem for b < O(1/(log s)^(d+2)).
This work has two contributions:
1. We strengthen Steinberger's result and show that any Santha-Vazirani source with bias b < O(1/(log n)^(w-2)) fools length n, width w read once branching programs. In other words, the strong independence assumption in the coin problem is completely redundant in the model of read once branching programs, assuming the bias remains small. That is, the exact same result holds for a much more general class of sources.
2. We tighten Aaronson's result and show that a depth d, size s Boolean circuit cannot solve the coin problem for b < O(1/(log s)^(d-1)). Moreover, our proof technique is different and we believe that it is simpler and more natural.