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


Event Speaker: 

Michael Forbes

Event Location: 


Event Date/Time: 

Thursday, April 17, 2014 - 10:30am

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.
Thesis Supervisor: Prof. Scott Aaronson

Relevant URL:
For more information please contact: Holly A Jones, <a href=""></a>