An improved derandomization of the switching lemma
An improved derandomization of the switching lemma
复制标题
改进的切换引理去随机化
DOI：
10.1145/3406325.3451054
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Kelley, Zander
中科院分区：
文献类型：
--
作者：
Kelley, Zander
我们证明了一个新的去随机化的Håstad的开关引理，展示了如何有效地产生限制满足开关引理的DNF或CNF公式的sizemusing只有O（logm）的随机位。开关引理的去随机化在许多工作中是有用的，作为构造对象的关键构件，这些对象在某种程度上相对于AC 0-电路是可证明伪随机的。这里，我们使用我们的新的去随机化来给出Trevisan和Xue的AC 0-电路的伪随机生成器（CCC'13）的改进分析：我们证明了生成器ε-仅用O（log（m/ε）D· logn）个随机比特就能欺骗n位输入的长度为m，深度为D的电路.特别地，我们得到（模的对数因子隐藏在O-符号）的依赖于m/ε这是最好的可能相对于目前已知的AC 0-电路的下限。
We prove a new derandomization of Håstad’s switching lemma, showing how to efficiently generate restrictions satisfying the switching lemma for DNF or CNF formulas of sizemusing onlyO(logm) random bits. Derandomizations of the switching lemma have been useful in many works as a key building-block for constructing objects which are in some way provably-pseudorandom with respect to AC0-circuits.Here, we use our new derandomization to give an improved analysis of the pseudorandom generator of Trevisan and Xue for AC0-circuits (CCC’13): we show that the generator ε-fools size-m, depth-Dcircuits withn-bit inputs using onlyO(log(m/ε)D· logn) random bits. In particular, we obtain (modulo the loglog-factors hidden in theO-notation) a dependence onm/ε which is best-possible with respect to currently-known AC0-circuit lower bounds.
登录
查看更多内容
通过轻度随机限制进行决策列表压缩
DOI：
10.1145/3357713.3384241
发表时间：
2020
期刊：
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020
影响因子：
--
作者：
Lovett, Shachar;Wu, Kewen;Zhang, Jiapeng
通讯作者：
Zhang, Jiapeng
去随机化的切换引理和改进的 AC0 去随机化
DOI：
--
发表时间：
2013
期刊：
2013 IEEE Conference on Computational Complexity
影响因子：
--
作者：
L. Trevisan;Tongke Xue
通讯作者：
Tongke Xue
起重
影响因子：
3.3
作者：
Denise R. McLane
通讯作者：
Denise R. McLane
恒定深度电路和多项式的量化去随机化的改进界限
影响因子：
1.4
作者：
R. Tell
通讯作者：
R. Tell
改进的深度 2 电路伪随机发生器
DOI：
--
发表时间：
2010
期刊：
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
作者：
Anindya De;Omid Etesami;Luca Trevisan;Madhur Tulsiani
通讯作者：
Madhur Tulsiani