- Hitting Sets for Multilinea...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in May 2014
Hitting Sets for Multilinear Read-Once Algebraic Branching Programs, in any Order
Speaker:
Michael Forbes
Date: Thursday, May 29, 2014
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Public: Yes
Location: 32-G575
Event Type:
Room Description:
Host: Ilya Razenshteyn
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Speaker URL: None
Speaker Photo:
None
Reminders to:
theory-seminars@csail.mit.edu, seminars@csail.mit.edu
Reminder Subject:
TALK: Hitting Sets 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).
Research Areas:
Impact Areas:
Created by Rebecca Yadegar 
at Tuesday, May 27, 2014 at 10:37 AM.