{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreia2hvolzxt5j3oilp2fsgkidafsv2xbu55s47rlmjzuv3mdkf6rqa",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mekn4gikhr62"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.10030v1",
  "publishedAt": "2026-02-11T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Gil Cohen",
    "Dean Doron",
    "Noam Goldgraber"
  ],
  "textContent": "**Authors:** Gil Cohen, Dean Doron, Noam Goldgraber\n\nPseudorandom generators (PRGs) for low-degree polynomials are a central object in pseudorandomness, with applications to circuit lower bounds and derandomization. Viola's celebrated construction 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 constructed PRGs with optimal seed length over fields of size exponential in $d$. The latter builds on the framework of Derksen and Viola, 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 sufficiently large characteristic. Our construction follows the framework of prior work and reduces the required field size by replacing the hitting-set generator used in previous constructions 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": "Optimal PRGs for Low-Degree Polynomials over Polynomial-Size Fields"
}