New Results on Noncommutative and Commutative Polynomial Identity Testing

Using ideas from automata theory we design a new efficient (deterministic) identity test for the noncommutative polynomial identity testing problem (first introduced and studied in [RS05, BW05]). More precisely, given as input a noncommutative circuit C{x₁, ldrldrldr , x_n} computing a polynomial in F{x₁, ldrldrldr , x_n} of degree d with at most t monomials, where the variables x_i are noncommuting, we give a deterministic polynomial identity test that checks if C equiv 0 and runs in time polynomial in d, n, |C|, and t. The same methods works in a black-box setting: given a noncommuting black-box polynomial f isin F{x₁, ldrldrldr , x_n} of degree d with t monomials we can, in fact, reconstruct the entire polynomial f in time polynomial in n, d and t. Indeed, we apply this idea to the reconstruction of black-box noncommuting algebraic branching programs (the ABPs considered by Nisan in [N91] and Raz-Shpilka in [RS05]). Assuming that the black-box model allows us to query the ABP for the output at any given gate then we can reconstruct an (equivalent) ABP in deterministic polynomial time. Finally, we turn to commutative identity testing and explore the complexity of the problem when the coefficients of the input polynomial come from an arbitrary finite commutative ring with unity whose elements are uniformly encoded as strings and the ring operations are given by an oracle. We show that several algorithmic results for polynomial identity testing over fields also hold when the coefficients come from such finite rings.

1 Introduction

Polynomial identity testing (denoted PIT) over fields is a well studied algorithmic problem: given an arithmetic circuit computing a polynomial in over a field , the problem is to determine whether the polynomial computed by is identically zero. The problem is also studied when the input polynomial is given only via black-box access. I.e. we can evaluate it at any point in or in for a field extension of . When is given by a circuit the problem is in randomized polynomial time. Even in the black-box setting, when is suitably larger than , the problem is in randomized polynomial time. A major challenge it to obtain deterministic polynomial time algorithms even for restricted versions of the problem. The results of Impagliazzo and Kabanets [KI03] show that the problem is as hard as proving superpoly-nomial circuit lower bounds. Indeed, the problem remains open even for depth-3 arithmetic circuits with an unbounded gate as output [DS05], [KS07].