text: We study the problem of obtaining deterministic black-box polynomial identity testing algorithms (PIT) for algebraic branching programs (ABPs) that are read-once and oblivious. This class has an deterministic white-box polynomial identity testing algorithm (due to Raz and Shpilka), but prior to this work there was no known such black-box algorithm. The main result of this work gives the first quasi-polynomial sized hitting sets for size S circuits from this class, when the order of the variables is known. As our hitting set is of size exp(lg^2 S), this is analogous (in the terminology of boolean pseudorandomness) to a seed-length of lg^2 S, which is the seed length of the pseudorandom generators of Nisan and Impagliazzo-Nisan-Wigderson for read-once oblivious boolean branching programs. Our results are stronger for branching programs of bounded width, where we give a hitting set of size exp(lg^2 S lglg S), corresponding to a seed length of lg^2 S lglg S. This is in stark contrast to the known results for read-once oblivious boolean branching programs of bounded width, where no pseudorandom generator (or hitting set) with seed length o(lg^2 S) is known. In follow up work, we strengthened a result of Mulmuley, and showed that derandomizing a particular case of the Noether Normalization Lemma is reducible to black-box PIT of read-once oblivious ABPs. Using the results of the present work, this gives a derandomization of Noether Normalization in that case, which Mulmuley conjectured would difficult due to its relations to problems in algebraic geometry. We also show that several other circuit classes can be black-box reduced to read-once oblivious ABPs, including set-multilinear ABPs (a generalization of depth-3 set-multilinear formulas), non-commutative ABPs (generalizing non-commutative formulas), and (semi-)diagonal depth-4 circuits (as introduced by Saxena).
  @cite_5: We define pseudorandom generators for Yao’s two-party communication complexity model and exhibit a simple construction, based on expanders, for it. We then use a recursive composition of such generators to obtain pseudorandom generators that fool distributed network algorithms. While the construction and the proofs are simple, we demonstrate the generality of such generators by giving several applications.
  @cite_15: Pseudorandom generators are constructed which convertO(SlogR) truly random bits toR bits that appear random to any algorithm that runs inSPACE(S). In particular, any randomized polynomial time algorithm that runs in spaceS can be simulated using onlyO(Slogn) random bits. An application of these generators is an explicit construction of universal traversal sequences (for arbitrary graphs) of lengthnO(logn).
summary: This work fits into the research program of derandomizing PIT, in particular derandomizing black-box PIT. However, for many of the models of algebraic circuits studied, there are corresponding boolean circuit models for which derandomization questions can also be asked. In particular, for a class @math of boolean circuits, we can seek to construct a @math for @math , such that for any circuit @math on @math inputs, we have the @math -closeness of distributions @math , where @math denotes the uniform distribution on @math . Nisan @cite_15 studied pseudorandom generators for space-bounded computation, and for space @math computation gave a generator with seed length @math . Impagliazzo, Nisan and Wigderson @cite_5 later gave a different construction with the same seed length. Randomized space-bounded computation can be modeled with read-once oblivious (boolean) branching programs, and these generators apply to this model of computation as well.