[CSDM] Michael Forbes at theory lunch this Friday

[Zeev Dvir]

Lunch is served at 11:45 with the talk starting at noon.

Room 402.

-zeev
-----------
Title: Pseudorandomness for Multilinear Read-Once 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 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 "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 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
"seed-length".  This constitutes the first quasipolynomial-time,
deterministic, black-box polynomial identity testing (PIT) algorithm for
this model.

Joint work with Ramprasad Saptharishi (MSR India) and Amir Shpilka
(Technion).
--------------
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/csdm/attachments/20130925/37545ecc/attachment.html>