Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness
复制标题
学习算法、电路下界和伪随机性之间的阴谋
DOI：
10.4230/lipics.ccc.2017.18
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
R. Santhanam
中科院分区：
文献类型：
--
作者：
I. Oliveira;R. Santhanam
我们证明了几个结果给新的和更强的学习，电路下界和伪随机性之间的联系。在其他结果中，我们展示了一个通用的学习加速引理，在指数时间和次指数时间机制中各种学习模型之间的等价性，学习和伪随机性之间的二分法，电路下界的非平凡学习的后果，概率指数时间的Karp-Lipton定理，以及最小电路尺寸问题的NC$^1$-硬度。
We prove several results giving new and stronger connections between learning, circuit lower bounds and pseudorandomness. Among other results, we show a generic learning speedup lemma, equivalences between various learning models in the exponential time and subexponential time regimes, a dichotomy between learning and pseudorandomness, consequences of non-trivial learning for circuit lower bounds, Karp-Lipton theorems for probabilistic exponential time, and NC$^1$-hardness for the Minimum Circuit Size Problem.
影响因子：
1.4
作者：
Eric Allender;D. Holden;Valentine Kabanets
通讯作者：
Eric Allender;D. Holden;Valentine Kabanets