Thesis Defense: Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs

Speaker: Michael Forbes

Date: Thursday, April 17, 2014

Time: 10:30 AM to 11:30 AM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Scott Aaronson, TOC, CSAIL, MIT

Contact: Holly A Jones, hjones01@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: toc@csail.mit.edu, seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: Thesis Defense: Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs

Title: Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs
Abstract: It is an important open question whether we can derandomize small space computation, that is, whether randomized logspace (RL) equals logspace (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.

In this thesis, we have considered an "algebraic" version of this question, where we seek deterministic algorithms for the "polynomial identity testing" problem for "read-once oblivious algebraic branching programs". This problem asks: given such a branching program, does it compute the zero polynomial? While this can be efficiently solved using randomness, constructing efficient deterministic algorithms is much more challenging.

In this defense, I'll discuss this model and give a deterministic algorithm for zero-testing, which can be seen as an analogue of Nisan's result for derandomizing RL. I'll also mention the applications of this algorithm to other models (low-rank tensors, non-commutative formulas, etc), other areas (Mulmuley's Geometric Complexity Theory program), and how the results can go beyond what is known in the analogous boolean model.

Research Areas:

Impact Areas:

This event is not part of a series.

Created by Holly A Jones at Friday, April 04, 2014 at 3:46 PM.