This is a survey of pseudorandomness, the theory of efficiently generating objects that" look
random" despite being constructed using little or no randomness. This theory has …

This is a survey of unconditional pseudorandom generators (PRGs). A PRG uses a short,
truly random seed to generate a long," pseudorandom" sequence of bits. To be more …

We study the problem of obtaining efficient, deterministic, black-box polynomial identity
testing algorithms (PIT) for algebraic branching programs (ABPs) that are read-once and …

A weighted pseudorandom generator (WPRG) is a generalization of a pseudorandom
generator (PRG) in which, roughly speaking, probabilities are replaced with weights that are …

We construct pseudorandom generators of seed length Õ (log (n)· log (1/є)) that є-fool
ordered read-once branching programs (ROBPs) of width 3 and length n. For unordered …

We present an iterative approach to constructing pseudorandom generators, based on the
repeated application of mild pseudorandom restrictions. We use this template to construct …

We give deterministic black-box polynomial identity testing algorithms for multilinear read-
once oblivious algebraic branching programs (ROABPs), in n O (log2 n) time. Further, our …

A recent paper of Braverman, Cohen, and Garg (STOC 2018) introduced the concept of a
weighted pseudorandom generator (WPRG), which amounts to a pseudorandom generator …

The Coin Problem is the following problem: a coin is given, which lands on head with
probability either 1/2+ β or 1/2-β. We are given the outcome of n independent tosses of this …

We present an explicit pseudorandom generator for oblivious, read-once, permutation
branching programs of constant width that can read their input bits in any order. The seed …