标题： 新的伪随机生成器和使用提取器的相关性界限 显示英文标题

标题： New Pseudorandom Generators and Correlation Bounds Using Extractors

摘要： 我们建立了针对一组计算模型的新相关性界限和伪随机生成器。 这些模型都是结构化低次数$F_2$-多项式的自然推广，我们在之前没有针对它们的相关性界限。 特别是： 1. 我们为宽度为2的$poly(n)$-长度分支程序构造了一个PRG，每次读取$d$位，种子长度为$2^{O(\sqrt{\log n})}\cdot d^2\log^2(1/\epsilon)$。 这在$d$和$\log(1/\epsilon)$方面接近最优的二次依赖。 之前的PRG由Bogdanov、Dvir、Verbin和Yehudayoff提出，其对$d$的依赖性指数级地更差，种子长度为$O(d\log n + d2^d\log(1/\epsilon))$。 2. 我们提供了针对大小为$n^{\Omega(\log n)}$的AC0电路的相关性界限和PRGs，该电路要么包含$n^{.99}$个SYM门（计算任意对称函数），要么包含$n^{.49}$个THR门（计算任意线性阈值函数）。 先前Servedio和Tan的工作仅处理了$n^{.49}$个SYM门或$n^{.24}$个THR门，而Lovett和Srinivasan的先前工作仅处理了多项式大小的电路。 3. 我们给出针对在输入分割为$n^{.99}$个部分的某些划分上的度数$n^{O(1)}$$F_2$-多项式集合的指数级小相关性界限（注意到在$n$个部分时，我们恢复了所有低次多项式）。 这一结果推广了针对在固定分割为$d$个块上的度数$(d-1)$的集合-多线性多项式的相关性界限，这些界限由 Bhrushundi、Harsha、Hatami、Kopparty 和 Kumar 建立。 所有这些结果背后的共同技术是用适当类型的提取器来强化一个困难函数，以获得更强的相关性界限。 尽管该技术已在之前的工作中使用过，但它依赖于在随机限制下模型缩小到一个非常小的类。 我们的结果表明，即使对于不具有这种行为的类，也可以进行这样的强化。 显示英文摘要

摘要： We establish new correlation bounds and pseudorandom generators for a collection of computation models. These models are all natural generalizations of structured low-degree $F_2$-polynomials that we did not have correlation bounds for before. In particular: 1. We construct a PRG for width-2 $poly(n)$-length branching programs which read $d$ bits at a time with seed length $2^{O(\sqrt{\log n})}\cdot d^2\log^2(1/\epsilon)$. This comes quadratically close to optimal dependence in $d$ and $\log(1/\epsilon)$. The previous PRG by Bogdanov, Dvir, Verbin, and Yehudayoff had an exponentially worse dependence on $d$ with seed length of $O(d\log n + d2^d\log(1/\epsilon))$. 2. We provide correlation bounds and PRGs against size-$n^{\Omega(\log n)}$ AC0 circuits with either $n^{.99}$ SYM gates (computing an arbitrary symmetric function) or $n^{.49}$ THR gates (computing an arbitrary linear threshold function). Previous work of Servedio and Tan only handled $n^{.49}$ SYM gates or $n^{.24}$ THR gates, and previous work of Lovett and Srinivasan only handled polysize circuits. 3. We give exponentially small correlation bounds against degree-$n^{O(1)}$ $F_2$-polynomials set-multilinear over some partition of the input into $n^{.99}$ parts (noting that at $n$ parts, we recover all low-degree polynomials). This generalizes correlation bounds against degree-$(d-1)$ polynomials which are set-multilinear over a fixed partition into $d$ blocks, which were established by Bhrushundi, Harsha, Hatami, Kopparty and Kumar. The common technique behind all of these results is to fortify a hard function with the right type of extractor to obtain stronger correlation bounds. Although this technique has been used in previous work, it relies on the model shrinking to a very small class under random restrictions. Our results show such fortification can be done even for classes that do not enjoy such behavior.