<div dir="ltr">Lunch is served at 11:45 with the talk starting at noon. <div><br></div><div>Room 402.</div><div><br></div><div>-zeev</div><div>-----------</div><div><span style="font-family:arial,sans-serif;font-size:16px">Title: Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order</span><br style="font-family:arial,sans-serif;font-size:16px">

<br style="font-family:arial,sans-serif;font-size:16px"><span style="font-family:arial,sans-serif;font-size:16px">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 read-once oblivious branching programs.  There are well-known results in this area (due to Nisan, and Impagliazzo-Nisan-Wigderson), but they fail to achieve optimal seed-length.  Further, it has been observed that these pseudorandom generators depend strongly on the &quot;order&quot; of the &quot;reads&quot; of the branching program. When this order is allowed to vary, only much weaker results are known.</span><br style="font-family:arial,sans-serif;font-size:16px">

<br style="font-family:arial,sans-serif;font-size:16px"><span style="font-family:arial,sans-serif;font-size:16px">In this work, we consider an &quot;algebraic&quot; version of this question.  That is, we seek to fool read-once algebraic branching programs, regardless of the variable order.  By rephrasing and improving the techniques of Agrawal-Saha-Saxena, we are able to construct hitting sets for multilinear polynomials in this unknown-order model that have polylogarithmic &quot;seed-length&quot;.  This constitutes the first quasipolynomial-time, deterministic, black-box polynomial identity testing (PIT) algorithm for this model.</span><br style="font-family:arial,sans-serif;font-size:16px">

<br style="font-family:arial,sans-serif;font-size:16px"><span style="font-family:arial,sans-serif;font-size:16px">Joint work with Ramprasad Saptharishi (MSR India) and Amir Shpilka (Technion).</span><br style="font-family:arial,sans-serif;font-size:16px">

</div><div><span style="font-family:arial,sans-serif;font-size:16px">--------------</span></div></div>