MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


I am looking for a survey on the state of the art in pseudorandom generators vs

(1) constant depth circuits and/or (2) Branching Programs

For (1), is "Anindya De, Omid Etesami, Luca Trevisan and Madhur Tulsiani Improved Pseudorandom Generators for Depth 2 Circuits" state of the art?

For (2), given that Barrington's theorem states that width-5 poly size branching programs = NC1 in power; what limited model of branching programs is studied in terms of fooling branching programs with pseudorandom generators?


share|cite|improve this question
I would guess you'd get more and quicker responses at – Will Jagy Oct 23 '11 at 20:48

For (1), their result is for depth 2 Circuits and is the best known so far. For more general constant-depth circuit, you may want to look at

Mark Braverman: Poly-logarithmic independence fools AC0 circuits

Barrington proved width-5 poly size multiple read branching programs = NC1. But people usually only talk about fooling read-once branching programs, i.e. each variable is read at most once.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.