← 研踪 PaperTrailarXiv:2602.10030 · v2
Optimal PRGs for Low-Degree Polynomials over Polynomial-Size Fields
首次提交 2026-02-11 01:52
版本更新 2026-11-02 04:19
雷达观测 2026-11-04 23:43
摘要
We construct the first pseudorandom generator (PRG) with optimal seed length for degree-$d$ polynomials over fields of size $q \approx d^4$, with no restriction on the characteristic. This improves on the construction of Dwivedi, Guo, and Volk (RANDOM 2024), which requires fields of size exponential in $d$ and sufficiently large characteristic, and on that of Derksen and Viola (FOCS 2022), which requires a field size that grows with the number of variables $n$. A recent breakthrough by Chattopadhyay, Hatami, Lee, Lovett, Tal, and Viola (ECCC 2026) gives a PRG over the binary field with seed length $\widetilde{O}(d^2\log^2 n)$, with subsequent work by Cohen (ECCC 2026) achieving seed length $O(d^4\log n)$. Both constructions use polarized random walks, and the current analyses incur at least a quadratic dependence on $d$. Our second result is a reduction that provides an alternative route to nearly optimal seed length over the binary field through improved constructions over larger fields. Specifically, we prove that, for any $δ\in (0,1)$, an optimal-seed PRG for degree-$d$ polynomials over fields of characteristic two and size $q \approx d^δ$ would yield a PRG over the binary field with seed length $O(d^{1/(1-δ)}\log n)$.
作者备注：arXiv admin note: text overlap with arXiv:2402.11915 by other authors
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-02 04:19 · 最新观测版本
Optimal PRGs for Low-Degree Polynomials over Polynomial-Size Fields
We construct the first pseudorandom generator (PRG) with optimal seed length for degree-$d$ polynomials over fields of size $q \approx d^4$, with no restriction on the characteristic. This improves on the construction of Dwivedi, Guo, and Volk (RANDOM 2024), which requires fields of size exponential in $d$ and sufficiently large characteristic, and on that of Derksen and Viola (FOCS 2022), which requires a field size that grows with the number of variables $n$. A recent breakthrough by Chattopadhyay, Hatami, Lee, Lovett, Tal, and Viola (ECCC 2026) gives a PRG over the binary field with seed length $\widetilde{O}(d^2\log^2 n)$, with subsequent work by Cohen (ECCC 2026) achieving seed length $O(d^4\log n)$. Both constructions use polarized random walks, and the current analyses incur at least a quadratic dependence on $d$. Our second result is a reduction that provides an alternative route to nearly optimal seed length over the binary field through improved constructions over larger fields. Specifically, we prove that, for any $δ\in (0,1)$, an optimal-seed PRG for degree-$d$ polynomials over fields of characteristic two and size $q \approx d^δ$ would yield a PRG over the binary field with seed length $O(d^{1/(1-δ)}\log n)$.
查看此版本解读 →查看此版本原文 ↗