- Thesis Defense: Polynomial ...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in April 2014

## 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

**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.