New Pseudorandom Generators and Correlation Bounds Using Extractors
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912178004557824 |
|---|---|
| author | Kumar, Vinayak M. |
| author_facet | Kumar, Vinayak M. |
| contents | 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/ε)$. This comes quadratically close to optimal dependence in $d$ and $\log(1/ε)$. 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/ε))$.
2. We provide correlation bounds and PRGs against size-$n^{Ω(\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_02653 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | New Pseudorandom Generators and Correlation Bounds Using Extractors Kumar, Vinayak M. Computational Complexity 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/ε)$. This comes quadratically close to optimal dependence in $d$ and $\log(1/ε)$. 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/ε))$. 2. We provide correlation bounds and PRGs against size-$n^{Ω(\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. |
| title | New Pseudorandom Generators and Correlation Bounds Using Extractors |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2501.02653 |