Guest Column: correlation bounds for polynomials over {0 1}
Guest Column: correlation bounds for polynomials over {0 1}
复制标题
来宾列：{0 1} 上多项式的相关界限
DOI：
10.1145/1515698.1515709
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Emanuele Viola
中科院分区：
文献类型：
--
作者：
Emanuele Viola
本文对在{0, 1}上展示与低次多项式相关性较小的显式函数这一基本挑战的最新进展进行了统一阐述。它讨论了长期存在的结果和近期的发展、相关的证明技术以及与伪随机生成器的联系。它还提出了几个研究方向。
This article is a unified treatment of the state-of-the-art on the fundamental challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over {0 1 }. It discusses long-standing results and recent developments, related proof techniques, and connections with pseudorandom generators. It also suggests several research directions.