2026-07-23T17:28:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14296 2024-03-06T10:53:54Z ddc:004 open_access

Error Reduction for Weighted PRGs Against Read Once Branching Programs Cohen, Gil Doron, Dean Renard, Oren Sberlo, Ori Ta-Shma, Amnon Pseudorandom generators Read once branching programs Space-bounded computation Weighted pseudorandom generators (WPRGs), introduced by Braverman, Cohen and Garg [Braverman et al., 2020], are a generalization of pseudorandom generators (PRGs) in which arbitrary real weights are considered, rather than a probability mass. Braverman et al. constructed WPRGs against read once branching programs (ROBPs) with near-optimal dependence on the error parameter. Chattopadhyay and Liao [Eshan Chattopadhyay and Jyun-Jie Liao, 2020] somewhat simplified the technically involved BCG construction, also obtaining some improvement in parameters. In this work we devise an error reduction procedure for PRGs against ROBPs. More precisely, our procedure transforms any PRG against length n width w ROBP with error 1/poly(n) having seed length s to a WPRG with seed length s + O(logw/(ε) ⋅ log log1/(ε)). By instantiating our procedure with Nisan’s PRG [Noam Nisan, 1992] we obtain a WPRG with seed length O(log{n} ⋅ log(nw) + logw/(ε) ⋅ log log 1/(ε)). This improves upon [Braverman et al., 2020] and is incomparable with [Eshan Chattopadhyay and Jyun-Jie Liao, 2020]. Our construction is significantly simpler on the technical side and is conceptually cleaner. Another advantage of our construction is its low space complexity O(log{nw})+poly(log log1/(ε)) which is logarithmic in n for interesting values of the error parameter ε. Previous constructions (like [Braverman et al., 2020; Eshan Chattopadhyay and Jyun-Jie Liao, 2020]) specify the seed length but not the space complexity, though it is plausible they can also achieve such (or close) space complexity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gil Cohen and Dean Doron and Oren Renard and Ori Sberlo and Amnon Ta-Shma 2021 Is Part Of LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2021.22 urn:nbn:de:0030-drops-142963 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.22 eng https://creativecommons.org/licenses/by/4.0/legalcode