XOR lemmas for resilient functions against polynomials
XOR lemmas for resilient functions against polynomials
复制标题
针对多项式的弹性函数的异或引理
DOI：
10.1145/3357713.3384242
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Zuckerman, David
中科院分区：
文献类型：
--
作者：
Chattopadhyay, Eshan;Hatami, Pooya;Hosseini, Kaave;Lovett, Shachar;Zuckerman, David
复杂性理论中的一个主要挑战是显式地构造与F2上的低次多项式具有小相关性的函数。我们介绍了一种新的技术来证明这样的F2多项式的相关界。使用这种技术，我们绑定的相关性的异或的多数与常次数多项式。事实上，我们证明了一个更一般的XOR引理，扩展到任意弹性功能。我们猜想该方法也可以推广到高阶多项式，其中的一个关键部分是关于F2上低次多项式Fourier谱的结构性结果.我们证明了对于任意n元多项式F2的次数至多为d，存在一个小的变量集S ∈ [n]，使得几乎所有的傅立叶质量都在与S相交的傅立叶系数上。事实上，我们的结果是更一般的，并发现这样的集合S的任何低维子空间的多项式。这种普遍性在推导新的XOR引理时是至关重要的。
A major challenge in complexity theory is to explicitly construct functions that have small correlation with low-degree polynomials over F2. We introduce a new technique to prove such correlation bounds with F2polynomials. Using this technique, we bound the correlation of an XOR of Majorities with constant degree polynomials. In fact, we prove a more general XOR lemma that extends to arbitrary resilient functions. We conjecture that the technique generalizes to higher degree polynomials as well.A key ingredient in our new approach is a structural result about the Fourier spectrum of low degree polynomials over F2. We show that for anyn-variate polynomialpover F2of degree at mostd, there is a small setS⊂ [n] of variables, such that almost all of the Fourier mass ofplies on Fourier coefficients that intersect withS. In fact our result is more general, and finds such a setSfor any low-dimensional subspace of polynomials. This generality is crucial in deriving the new XOR lemmas.
登录
查看更多内容
来宾列：{0 1} 上多项式的相关界限
DOI：
10.1145/1515698.1515709
发表时间：
2009
期刊：
SIGACT News
影响因子：
--
作者：
Emanuele Viola
通讯作者：
Emanuele Viola
CC0[p] 的伪随机生成器和有限域上低次多项式的傅里叶谱
DOI：
--
发表时间：
2010
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Shachar Lovett;P. Mukhopadhyay;Amir Shpilka
通讯作者：
Amir Shpilka
电路深度减少
DOI：
--
发表时间：
2018
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Alexander Golovnev;A. Kulikov
通讯作者：
A. Kulikov
第二傅立叶级伪随机发生器及其在具有奇偶校验门的 AC0 中的应用
DOI：
--
发表时间：
2019
期刊：
(ITCS
影响因子：
--
作者：
Chattopadhyay, Eshan;Hatami, Pooya;Lovett, Shachar;Tal, Avishay
通讯作者：
Tal, Avishay
关于低次多项式的表示
DOI：
--
发表时间：
1993
期刊：
Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science
影响因子：
--
作者：
R. Smolensky
通讯作者：
R. Smolensky