{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreietpsajct6aojjhpfhvrjrdrjzmrl7i524ncxnabyby6pih7a3lz4",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mkrjleunbg62"
  },
  "path": "/report/2026/064",
  "publishedAt": "2026-04-30T18:23:32.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "Breaking the log-squared barrier in pseudorandom generator constructions for read-once branching programs, namely, achieving seed length $o(\\log^2 n)$ for length-$n$ programs, has remained a longstanding open problem since Nisan's seminal construction. We show that breaking this barrier, even achieving seed length $O(\\log^{3/2} n)$ (for, say, constant width), would follow from simultaneously improving the dependence of PRGs on two seemingly secondary parameters: the error $\\varepsilon$ and the program's arity $|\\Sigma|$. Such improved dependence is already achieved by certain weighted PRGs (WPRGs). This reduces the problem of breaking the log-squared barrier to deweightization: closing the gap between PRG and WPRG constructions. While the importance of the error parameter has been recognized over the past decade, the role of the arity $|\\Sigma|$ has largely been overlooked. By inspection, several existing WPRG constructions achieve optimal dependence on $\\Sigma$, though the state-of-the-art constructions do not. As our second result, we construct WPRGs that attain optimal dependence on $\\Sigma$ while matching the best known bounds in all other parameters.",
  "title": "TR26-064 |  Toward Improving Nisan’s PRG via Deweightization | \n\n\tben chen, \n\n\tGil Cohen, \n\n\tDean Doron, \n\n\tYuval Khaskelberg, \n\n\tAmnon Ta-Shma"
}