1
$\begingroup$

Hi.

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?

Thanks!

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .