TALK: Algs. & Complexity Seminar/ Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order Speaker: Michael Forbes

Speaker: Michael Forbes , MIT

Date: Thursday, October 31, 2013

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32 G451

Event Type:

Room Description:

Host: Ilya Razenshteyn

Contact: Ilya Razenshteyn, ilyaraz@MIT.EDU

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: compalgsem@lists.csail.mit.edu, csail, seminars@csail.mit.edu

Reminder Subject: TALK: TALK: Algs. & Complexity Seminar/ Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order Speaker: Michael Forbes

It is an important open question whether we can derandomize small spacecomputation, that is, whether RL equals L. One version of this question isto 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).

Research Areas:

Impact Areas:

This event is not part of a series.

Created by Nina L. Olff at Tuesday, October 29, 2013 at 9:10 AM.