The Distinguishability of Product Distributions by Read-Once Branching Programs
The Distinguishability of Product Distributions by Read-Once Branching Programs
复制标题
通过一次读取分支程序区分产品分布
DOI：
10.1109/ccc.2013.33
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
J. Steinberger
中科院分区：
文献类型：
--
作者：
J. Steinberger
我们改进了布罗迪（Brody）和韦尔宾（Verbin）在2010年FOCS会议上关于常宽度分支程序区分乘积分布能力的主要结果。具体来说，我们表明，对于宽度为\(w\)、长度为\(n\)的一次性读取分支程序（对于每个常数\(w\)），一枚硬币必须具有至少\(\Omega(1 / \log(n)^{\omega - 2})\)的偏差才能与一枚公平硬币区分开来，这是一个紧界。我们的结果引入了新技术，特别是一种新颖的“交织混合”技术和一种“程序随机化”技术，这两种技术在我们的证明中都起着关键作用。利用相同的技术，我们还成功地给出了由宽度为\(w\)的一次性读取分支程序可计算的单调函数的最大影响的紧上界。
We improve the main result of Brody and Verbin from FOCS 2010 on the power of constant-width branching programs to distinguish product distributions. Specifically, we show that a coin must have bias at least Ω(1/log(n)ω-2) to be distinguishable from a fair coin by a width w, length n read-once branching program (for each constant w), which is a tight bound. Our result introduces new techniques, in particular a novel "interwoven hybrid" technique and a "program randomization" technique, both of which play crucial roles in our proof. Using the same techniques, we also succeed in giving tight upper bounds on the maximum influence of monotone functions computable by width w read-once branching programs.