Fourier bounds and pseudorandom generators for product tests
Fourier bounds and pseudorandom generators for product tests
复制标题
用于产品测试的傅里叶界和伪随机生成器
DOI：
10.4230/lipics.ccc.2019.7
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Chin Ho Lee
中科院分区：
文献类型：
--
作者：
Chin Ho Lee
我们研究函数f：{0，1}mk→{-1，0，1}的傅里叶谱，它可以写成k个布尔函数fi在不相交的m比特输入上的乘积。我们证明了对于每个正整数d，我们的上界紧到O(·)中的一个常数因子。我们的证明使用Schur-凸性，并建立在一个新的“d级不等式”的基础上，对于任何[0，1]值函数f，它的上界是关于它的期望的，这可能是独立的。作为结果，我们构造了这类函数的伪随机生成器，其种子长度为(m+log(k/ε))，在logm、logk和loglog(1/ε)中是最优的多项式因子。我们的生成器尤其适用于研究得很好的组合矩形类，此外，我们还允许以任何顺序读取位。即使对于这种特殊情况，以前的生成器在其种子长度中也有一个额外的(LOG(1/ε))因子。我们还将我们的结果推广到取值范围为[-1，1]的函数FI。
We study the Fourier spectrum of functions f: {0, 1}mk → { -1, 0, 1} which can be written as a product of k Boolean functions fi on disjoint m-bit inputs. We prove that for every positive integer d, [EQUATION] Our upper bounds are tight up to a constant factor in the O(·). Our proof uses Schur-convexity, and builds on a new "level-d inequality" that bounds above [EQUATION] for any [0, 1]-valued function f in terms of its expectation, which may be of independent interest. As a result, we construct pseudorandom generators for such functions with seed length Õ(m + log(k/ε)), which is optimal up to polynomial factors in log m, log log k and log log(1/ε). Our generator in particular works for the well-studied class of combinatorial rectangles, where in addition we allow the bits to be read in any order. Even for this special case, previous generators have an extra Õ(log(1/ε)) factor in their seed lengths. We also extend our results to functions fi whose range is [-1, 1].
用于以任意顺序读取一次的分支程序的伪随机生成器
DOI：
10.1109/focs.2018.00093
发表时间：
2018
期刊：
59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018
影响因子：
--
作者：
Forbes, Michael A.;Kelley, Zander
通讯作者：
Kelley, Zander
第二傅立叶级伪随机发生器及其在具有奇偶校验门的 AC0 中的应用
DOI：
--
发表时间：
2019
期刊：
(ITCS
影响因子：
--
作者：
Chattopadhyay, Eshan;Hatami, Pooya;Lovett, Shachar;Tal, Avishay
通讯作者：
Tal, Avishay