{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreifralhzmsdpc2qzsppyqs6xatlqqxfswabgcw45lapkvvjtbxow3e",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mekgfemo4s62"
  },
  "path": "/report/2026/016",
  "publishedAt": "2026-02-10T10:59:17.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "Pseudorandom generators (PRGs) for low-degree polynomials are a central object in pseudorandomness, with applications to circuit lower bounds and derandomization. Viola’s celebrated construction (CC 2009) gives a PRG over the binary field, but with seed length exponential in the degree $d$. This exponential dependence can be avoided over sufficiently large fields. In particular, Dwivedi, Guo, and Volk (RANDOM 2024) constructed PRGs with optimal seed length over fields of size exponential in $d$. The latter builds on the framework of Derksen and Viola (FOCS 2022), who obtained optimal-seed constructions over fields of size polynomial in $d$, although growing with the number of variables $n$. In this work, we construct the first PRG with optimal seed length for degree-$d$ polynomials over fields of polynomial size, specifically $q \\approx d^4$, assuming, as in [DGV], sufficiently large characteristic. Our construction follows the framework of [DV, DGV] and reduces the required field size by replacing the hitting-set generator used in prior work with a new pseudorandom object. We also observe a threshold phenomenon in the field-size dependence. Specifically, we prove that constructing PRGs over fields of sublinear size, for example $q = d^{0.99}$ where $q$ is a power of two, would already yield PRGs for the binary field with comparable seed length via our reduction, provided that the construction imposes no restriction on the characteristic. While a breakdown of existing techniques has been noted before, we prove that this phenomenon is inherent to the problem itself, irrespective of the technique used.",
  "title": "TR26-016 |  Optimal PRGs for Low-Degree Polynomials over Polynomial-Size Fields | \n\n\tGil Cohen, \n\n\tDean Doron, \n\n\tNoam Goldgraber"
}