Fooling Polytopes
Fooling Polytopes
复制标题
欺骗多面体
DOI：
10.1145/3460532
复制
发表时间：
2022
影响因子：
2.5
通讯作者：
Tan, Li-Yang
中科院分区：
文献类型：
--
作者：
O’Donnell, Ryan;Servedio, Rocco A.;Tan, Li-Yang
我们给出了一个伪随机生成器，它可以在 {0, 1}n 上愚弄多面体，种子长度为 polylog(m) · logn。先前的最佳种子长度对m具有超线性依赖性。
We give a pseudorandom generator that foolsm-facet polytopes over {0, 1}nwith seed length polylog(m) · logn. The previous best seed length had superlinear dependence onm.
登录
查看更多内容
DOI：
--
发表时间：
2020
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Valentine Kabanets;Sajin Koroth;Zhenjian Lu;Dimitrios Myrisiotis;I. Oliveira
通讯作者：
I. Oliveira
每个线性阈值函数都有一个低权重逼近器
影响因子：
1.4
作者：
R. Servedio
通讯作者：
R. Servedio
多项式阈值函数的伪随机生成器
DOI：
10.1145/1806689.1806749
发表时间：
2009
期刊：
ArXiv
影响因子：
--
作者：
Raghu Meka;David Zuckerman
通讯作者：
David Zuckerman
通过离散傅立叶变换实现伪随机性
DOI：
10.1109/focs.2015.60
发表时间：
2015
期刊：
2015 IEEE 56th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Parikshit Gopalan;D. Kane;Raghu Meka
通讯作者：
Raghu Meka
DOI：
10.1145/1374376.1374450
发表时间：
2008
期刊：
Proceedings of the fortieth annual ACM symposium on Theory of computing
影响因子：
--
作者：
R. O'Donnell;R. Servedio
通讯作者：
R. Servedio