Notes of Anup Rao’s talk

Pseudorandom generators for regular branching programs

Fooling branching programs. A branching program is a {d} layer digraph, 2 directed edges, labelled {0} and {1}, 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 {d}. They are powerful: they simulate any randomized logspace computation.

To remove randomness, one merely needs to deterministically estimate the probability that output is {1}. Reingold’s derandomization of random walk is a special case.

Our approach: use

1. Pseudorandom generators

Definition 1 A map {\{ 0,1 \}^t \rightarrow \{ 0,1 \}^n} is an {\epsilon}-pseudorandom generator for a class {\mathcal{P}} of programs if for every {P\in\mathcal{P}}, {P(G(U_t))} is {\epsilon}-close to {P(U_n)}.

{t} is called the seed length. The smaller {t} (in terms of {n}), the better.

Goal: construct {G} to estimate {\mathop{\mathbb P}(output=1)} using additional space {t}.

2. Regular programs

Say a program is regular of every vertex has at most {2} edges coming in.

Example 1 Such programs still compute multiplication in a finite group.

Problem: Construct {G} with {t=\log n}, with various controls on depth.

3. Our results

Theorem 2 (Rao, Raz, Yehudayoff) We construct a pseudorandom generator expanding {\log(n)(\log d +\log\log n +\cdots)} bits to {n} bits, and which is efficient against width {d} 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 {\epsilon}-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 {t} bits to {n/2} bits. Trivially one gets from it a pseudorandom generator expanding {2t} bits to {n} bits. Idea is to partially derandomize this procedure, by letting the second copy of {G} work on the output of an extractor. Iterating the procedure gives a pseudorandom generator with seed length {(\log n)^2}.

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 {\log d} bits of the information contained in the input. Regularity is needed in the analysis.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s