Pseudorandom bits for constant depth circuits with few arbitrary symmetric gates
Pseudorandom bits for constant depth circuits with few arbitrary symmetric gates
复制标题
具有少量任意对称门的恒定深度电路的伪随机位
DOI：
10.1137/050640941
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Emanuele Viola
中科院分区：
文献类型：
--
作者：
Emanuele Viola
我们展示了一个显式可计算的“伪随机”生成器，它将l位扩展为m（l）= l/sup /spl Ω/（log l）/位，这些位对于具有log m（l）任意对称门（例如，PARITY、MAJORITY）的大小为m（l）的恒定深度电路来说看起来是随机的。这改进了吕比，Velickovic和Wigderson（ISTCS '93）的生成器，该生成器实现了相同的延伸，但仅在顶部使用一个任意对称门来愚弄深度为2的电路。我们的生成器比Nisan的恒定深度电路生成器（Combinatorica '91）更丰富的电路类别（但Nisan的生成器有更大的延伸）。特别是，我们得出结论，每个功能可计算的均匀聚（n）大小的概率常数深度电路与O（log n）任意对称门是在时间（2/sup no（1）/）这似乎是最丰富的概率电路类已知承认一个次指数去随机化。我们的生成器是通过构造一个显式函数f：{0，1}/sup n/ /spl rnl/ {0，1}来获得的，该函数对于大小为n/sup /spl epsi//spl middot/log n/的具有/spl epsi/log/sup 2/ n的任意对称门的恒定深度电路平均而言是非常困难的，并将其插入到Nisan-Wigderson伪随机生成器构造（FOCS '88）中。该函数的平均情况困难性的证明是Razborov和Wigderson（IPL '93）以及汉森和Miltersen（MFCS '04）对参数的修改，并结合了Hdstad的切换引理（STOC '86）和巴拜、Nisan和Szegedy（STOC '89）的多方通信复杂性下限。
We exhibit an explicitly computable 'pseudorandom' generator stretching l bits into m(l) = l/sup /spl Omega/(log l)/ bits that look random to constant-depth circuits of size m(l) with log m(l) arbitrary symmetric gates (e.g. PARITY, MAJORITY). This improves on a generator by Luby, Velickovic and Wigderson (ISTCS '93) that achieves the same stretch but only fools circuits of depth 2 with one arbitrary symmetric gate at the top. Our generator fools a strictly richer class of circuits than Nisan's generator for constant depth circuits (Combinatorica '91) (but Nisan's generator has a much bigger stretch). In particular, we conclude that every function computable by uniform poly(n)-size probabilistic constant depth circuits with O(log n) arbitrary symmetric gates is in TIME (2/sup no(1)/) This seems to be the richest probabilistic circuit class known to admit a subexponential derandomization. Our generator is obtained by constructing an explicit function f : {0, 1}/sup n/ /spl rarr/ {0, 1} that is very hard on aver-age for constant-depth circuits of size n/sup /spl epsi//spl middot/log n/ with /spl epsi/log/sup 2/ n it arbitrary symmetric gates, and plugging it into the Nisan-Wigderson pseudorandom generator construction (FOCS '88). The proof of the average-case hardness of this function is a modification of arguments by Razborov and Wigderson (IPL '93), and Hansen and Miltersen (MFCS '04), and combines Hdstad's switching lemma (STOC '86) with a multiparty communication complexity lower bound by Babai, Nisan and Szegedy (STOC '89).