Algebraic Complexity Seminar

Read-Once Oblivious Algebraic Branching Programs: Lower Bounds and Identity Testing (part II)

In this multi-part series, we will discuss a very simple model of algebraic computation: read-once algebraic branching programs.  This model naturally captures several other models: sums of powers of linear froms, low-rank tensors, non-commutative linear algebra (in some sense) and the Noether Normalization of simultaneously conjugating tuples of matrices.

We will discuss the above connections and then delve into this model. First, we will give exponential lower bounds for this model to compute an explicit polynomial. Then we will discuss the polynomial identity testing (PIT) problem: given a computation in the above form, decide whether it is zero.  I will then give a linear-algebra-based polynomial-time algorithm for this problem that is "non-oblivious".  I will then turn to the construction of "oblivious" algorithms (hitting sets) and give a quasi-polynomial-time oblivious algorithm.  This latter algorithm will be based on a natural pseudorandom object from linear algebra called a "rank extractor".