Speaker: Michael Forbes, M.I.T
Title: Hitting Sets for Multilinear ReadOnce Algebraic Branching Programs, in any Order
Abstract: It is an important open question whether we can derandomize small space computation, that is, whether RL equals L. One version of this question is to construct pseudorandom generators for readonce oblivious branching programs. There are wellknown results in this area (due to Nisan, and ImpagliazzoNisanWigderson), but they fail to achieve optimal seedlength. Further, it has been observed that these pseudorandom generators depend strongly on the "order" of the "reads" of the branching program. When this order is allowed to vary, only much weaker results are known.
In this work, we consider an "algebraic" version of this question. That is, we seek to fool readonce algebraic branching programs, regardless of the variable order. By rephrasing and improving the techniques of AgrawalSahaSaxena, we are able to construct hitting sets for multilinear polynomials in this unknownorder model that have polylogarithmic "seedlength". This constitutes the first quasipolynomialtime, deterministic, blackbox polynomial identity testing (PIT) algorithm for this model.
Joint work with Ramprasad Saptharishi (MSR India) and Amir Shpilka (Technion).
