Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




Computational Complexity - Research Seminar

Maurice Jansen: Deterministic Black-Box Identity Testing Ordered Algebraic Branching Programs

March 15, 2011, 11 a.m.
E 1 3, Room 415

In this talk we will consider the polynomial identity testing (PIT) problem, i.e. the problem of deciding whether a given multivariate polynomial is identical to the zero polynomial or not. Using randomization this problem can be efficiently solved using the Schwartz-Zippel-deMillo-Lipton Test. In recent years the question of derandomization of PIT has attracted considerable attention due to the fact that it provides a possible avenue towards proving circuit lower bounds. For the introduction some of these connections will be reviewed.

For the main result we study a restricted version of the PIT problem. We will consider algebraic branching programs (ABPs) with restrictions on the order and the number of reads of variables in the program. An ABP is given by a layered directed acyclic graph with source $s$ and sink $t$, whose edges are labeled by variables or field constants. It computes the sum of weights of all paths from $s$ to $t$, where the weight of a path is defined as the product of edge-labels on the path. For an ordered ABP, for all directed paths from the source to the sink, variables are restricted to appear in the same order (allowing omissions). One can think of the OABP as the arithmetic analogue of the well-known ordered binary decision diagram (OBDD). We say an ABP is of read $r$, if any variable appears at most $r$ times.

We show that in the black box model, i.e. given only query access to the polynomial, read $r$ ordered ABPs can be tested in $DTIME[2^{O(r\log r \cdot \log^2 n \log\log n)}]$. In other words, if the read is restricted to be polylogarithmic, we have a deterministic algorithm that runs in quasipolynomial time in the black box setting. To establish this result, we combine some basic tools from algebraic geometry with ideas from derandomization in the Boolean domain.

I will also report on some of the computational limitations of ordered ABPs, e.g. both the determinant and permanent require exponential size in this model.

This talk is based on joint work with Youming Qiao (Tsinghua University) and Jayalal Sarama (IIT Madras).