A Dichotomy for Local Small-Bias Generators

by Benny Applebaum, Andrej Bogdanov, and Alon Rosen

Oded's comments

This paper provides a characterization of predicates that, when coupled with a random graph, yield small-bias PRGs with super-linear stretch. This set of predicates contains a vast majority of all predicate of sufficient arity, whereas the rest (when coupled with a random graph) yield "bad PRGs" that fail linear tests (even if the stretch is only linear).

The original abstract

See ECCC TR11-126.


Back to list of Oded's choices.