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!

$\endgroup$
1

1 Answer 1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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