Pseudorandom generators for regular branching programs
Fooling branching programs. A branching program is a layer digraph, 2 directed edges, labelled and , emanate from each vertex. A string encodes a walk in the graph. Output is position at the end. Such programs compute e.g. linear functions mod . They are powerful: they simulate any randomized logspace computation.
To remove randomness, one merely needs to deterministically estimate the probability that output is . Reingold’s derandomization of random walk is a special case.
Our approach: use
1. Pseudorandom generators
Definition 1 A map is an -pseudorandom generator for a class of programs if for every , is -close to .
is called the seed length. The smaller (in terms of ), the better.
Goal: construct to estimate using additional space .
2. Regular programs
Say a program is regular of every vertex has at most edges coming in.
Example 1 Such programs still compute multiplication in a finite group.
Problem: Construct with , with various controls on depth.
3. Our results
Theorem 2 (Rao, Raz, Yehudayoff) We construct a pseudorandom generator expanding bits to bits, and which is efficient against width regular programs.
We use extractors. These gadgets take a non uniform distribution (if min-entropy bounded below), combine it with few random bits, and outputs an -uniform distribution of the same size.
There are plenty of constructions. We shall merely use the resulting gadget.
Suppose we have a pseudorandom generator expanding bits to bits. Trivially one gets from it a pseudorandom generator expanding bits to bits. Idea is to partially derandomize this procedure, by letting the second copy of work on the output of an extractor. Iterating the procedure gives a pseudorandom generator with seed length .
How can one do better ? Errors arise at each step of the iteration and add up. In the doubling step, if output is independant of the former (resp. latter) half of the input, error is much smaller. This should happen, since the program uses only bits of the information contained in the input. Regularity is needed in the analysis.