Small-Bias Spaces for Group Products
Small-Bias Spaces for Group Products
复制标题
群产品的小偏差空间
DOI：
10.1007/978-3-642-03685-9_49
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
David Zuckerman
中科院分区：
文献类型：
--
作者：
Raghu Meka;David Zuckerman
小偏差空间（small-bias space）在复杂性理论、编码理论和去随机化（derandomization）中有许多应用。我们将小偏差空间的概念推广到群积的情形。除了是自然的，我们的扩展捕获了一些困难，在构建伪随机生成器的恒定宽度分支程序-一个长期存在的开放问题。我们提供了一个有效的确定性建设的小偏置空间的可解群。我们的构造利用了可解群具有阿贝尔的非平凡正规子群这一事实，并建立在Azar等人[AMN 98]对阿贝尔群的构造上。对于任意的有限群，我们给出了一个有效的确定性结构，实现常数偏置。对于素数p，我们还构造了愚弄线性函数mod p的伪随机生成器。
Small-bias, or *** -biased, spaces have found many applications in complexity theory, coding theory, and derandomization. We generalize the notion of small-bias spaces to the setting of group products. Besides being natural, our extension captures some of the difficulties in constructing pseudorandom generators for constant-width branching programs - a longstanding open problem. We provide an efficient deterministic construction of small-bias spaces for solvable groups. Our construction exploits the fact that solvable groups have nontrivial normal subgroups that are abelian and builds on the construction of Azar et al. [AMN98] for abelian groups. For arbitrary finite groups, we give an efficient deterministic construction achieving constant bias. We also construct pseudorandom generators fooling linear functions mod p for primes p .