Luby-Veličković-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits
Luby-Veličković-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits
复制标题
回顾 Luby-Veličković-Wigderson：改进深度二电路的相关界限和伪随机生成器
DOI：
10.4230/lipics.approx-random.2018.56
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Li
中科院分区：
文献类型：
--
作者：
R. Servedio;Li
我们研究由$ \ mathsf {sym} $ - gate（计算任意对称函数）或$ \ mathsf {thr} $ - gate（计算任意线性阈值函数）的相关性界和伪发电机。这是由$ s $ $ \ mathsf {and} $门喂养的。在早期有影响力的工作中考虑了这种回路，该作品是针对Luby，Veli \ V {C} Kovi \'C和Wigderson [lvw93]的无条件降低的，他们给出了第一个具有种子长度的非平凡PRG，其种子长度$ 2^{o（\ sqrt {\ sqrt {\ sqrt { \ log（s/\ varepsilon）}）} $ $ \ varepsilon $ -Fools这些电路。
在这项工作中，我们获得了[lvw93]的种子长度的第一个严格改进：我们构造了一个$ \ varepsilon $ -fools size-size-$ s $ $ \ \ \ {\ symsf {sym}，\ mathsf {thr} \} \ circ \ mathsf {and} $ circuits $ \ {0,1 \}^n $带子长度\ [ 2^{o（\ sqrt {\ log s}）} + \ mathrm {polylog}（1/\ varepsilon），\ \] \ varepsilon $ depentence of [lvww93] 。上面的PRG实际上是一个更通用的PRG的特殊情况，我们为包含多个$ \ Mathsf {sym} $或$ \ Mathsf {thr} $ Gates的恒定电路建立，其中包括特殊情况$ \ {\ Mathsf {\ Mathsf {sym}，\ Mathsf {thr} \} \ Circ \ Mathsf {ac^0} $ Circuits。这些更一般的结果加强了中提琴的先前结果[VIO06]，并基本上增强了Lovett和Srinivasan [LS11]的最新结果。
我们改进的PRG遵循改进的相关界，这些范围通过Nisan-Wigderson“硬度与随机性”范式转化为PRG [NW94]。我们改进的相关范围的关键是使用最近由于H {\ aa} stad [H {h {\ aa} S14]而引起的最新功能\ emph {多旋转}引理。
We study correlation bounds and pseudorandom generators for depth-two circuits that consist of a $\mathsf{SYM}$-gate (computing an arbitrary symmetric function) or $\mathsf{THR}$-gate (computing an arbitrary linear threshold function) that is fed by $S$ $\mathsf{AND}$ gates. Such circuits were considered in early influential work on unconditional derandomization of Luby, Veli\v{c}kovi\'c, and Wigderson [LVW93], who gave the first non-trivial PRG with seed length $2^{O(\sqrt{\log(S/\varepsilon)})}$ that $\varepsilon$-fools these circuits.
In this work we obtain the first strict improvement of [LVW93]'s seed length: we construct a PRG that $\varepsilon$-fools size-$S$ $\{\mathsf{SYM},\mathsf{THR}\} \circ\mathsf{AND}$ circuits over $\{0,1\}^n$ with seed length \[ 2^{O(\sqrt{\log S })} + \mathrm{polylog}(1/\varepsilon), \] an exponential (and near-optimal) improvement of the $\varepsilon$-dependence of [LVW93]. The above PRG is actually a special case of a more general PRG which we establish for constant-depth circuits containing multiple $\mathsf{SYM}$ or $\mathsf{THR}$ gates, including as a special case $\{\mathsf{SYM},\mathsf{THR}\} \circ \mathsf{AC^0}$ circuits. These more general results strengthen previous results of Viola [Vio06] and essentially strengthen more recent results of Lovett and Srinivasan [LS11].
Our improved PRGs follow from improved correlation bounds, which are transformed into PRGs via the Nisan--Wigderson "hardness versus randomness" paradigm [NW94]. The key to our improved correlation bounds is the use of a recent powerful \emph{multi-switching} lemma due to H{\aa}stad [H{\aa}s14].