Thesis Defense: Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs
Date: Thursday, April 17, 2014
Time: 10:30 AM to 11:30 AM Note: all times are in the Eastern Time Zone
Host: Scott Aaronson, TOC, CSAIL, MIT
Contact: Holly A Jones, firstname.lastname@example.org
Speaker URL: None
email@example.com, firstname.lastname@example.org, email@example.com
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.
Created by Holly A Jones at Friday, April 04, 2014 at 3:46 PM.