Computer Science/Discrete Mathematics Seminar I

Polynomial Identity Testing (PIT) is the problem of identifying whether a given algebraic circuit computes the identically zero polynomial. It is well-known that this problem can be solved with small error probability by testing whether the circuit evaluates to zero on random evaluation points. Recently, there has been much interest in solving this problem deterministically, because it has close connections with circuit lower bounds, and this problem is now one of the frontiers of the area of pseudorandomness. The method of partial derivatives is a fairly successful technique for understanding algebraic computation. Nisan used this method to show exponential lower bounds for non-commutative branching programs, a natural model of computation at least as powerful as formulas. Later, Raz and Shpilka used the method develop a polynomial-time ``white box’’ PIT algorithm for non-commutative branching programs, where this algorithm can ``look’’ at the structure of the branching program. In this work, we extend the partial derivative method to the ``black box’’ PIT setting for read-once oblivious branching programs, by deriving a quasi-polynomial-time algorithm that solves PIT by only evaluating the branching program at chosen locations. As a corollary, we also derive similar results for non-commutative branching programs. Joint work with Amir Shpilka