Toward Improving Nisan's PRG via Deweightization

by ben chen, Gil Cohen, Dean Doron, Yuval Khaskelberg, and Amnon Ta-Shma.

Oded's comments

(Disclaimer: While I consider improving Noam's PRG to be one of the most interesting open problems in the field, I regret to admit that I do not master the research performed towards this direction in the last couple of decades. Hence, my understanding of this paper is extremely superficial; still, I found it educational to read its introduction and Sec 2.1 (while not daring to try reading Sec 2.2).)

The notion of a weighted PRG, introduced by Braverman, Cohen, and Garg, received quite a bit of attention in the last decades (see, e.g., HERE and HERE and Sec 4.2 in Hoza's survey on derandomizing BPL).

While the role of negative weights was observed before, the current work indicates that unbounded weights are crucial too (i.e., Thm 1.1 extended to weighted PRGs provided that the absolute value of these weights is bounded). Still, in both cases, having a role or being crucial only indicates that these issues pose obstacles to a specific construction (or to solving an artificially defined problem). Needless to say, alternative constructions can yield solutions to natural problems like the one solved (with weighted PRGs) in Cor 1.3.

To be fair, the paper is undecided about whether Cor 1.3 raises a challenge (to de-weighting) that can be met in the near future or indicates a natural separation between weighted and standard PRGs. The same holds with respect to the study of the dependence of PRG constructions on the output's alphabet size (which was set to 2 till now). I'm certainly not in position to speculate on these questions.

Original abstract

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.

See ECCC TR26-064.


Back to list of Oded's choices.