The Taub Faculty of Computer Science Events and Talks

Using ideas from automata theory we design a new efficient (deterministic) identity test for the noncommutative polynomial identity testing problem. More precisely, given as input a noncommutative circuit C computing a polynomial of degree d in the noncommutative ring F{x_1,x_2,...,x_n} with at most t monomials, where the variables x_i are noncommuting, we give a deterministic polynomial identity test that checks if C=0 and runs in time polynomial in d, n, size(C), and t. Prior to our work, the only known deterministic polynomial time identity testing algorithm in the noncommutative model was for noncommutative formulas (Raz and Shpilka 2005). If fact we show similar ideas can be used to design a deterministic polynomial time interpolation algorithm for such polynomials.

Extending the automata theoretic ideas, we design a new randomized polynomial time algorithm for noncommutative circuit computing small degree polynomial. This algorithm is based on isolation lemma and conceptually quite different from the existing algorithm due to Bogdanov and Wee (2005). Using this algorithm, we show that derandomization of a particular instance of isolation lemma yields circuit lower bound in noncommutative model. This is similar in flavour to the Impagliazzo-Kabanets (2003) result for commutative case.

We further show that the derandomization of a stronger version of an instance of isolation lemma implies that an explicit multilinear polynomial in usual commutative model does not have subexponential size arithmetic circuit. This result is similar in flavor to the Manindra Agrawal's (2005) result that a black-box derandomization of polynomial identity testing for a class of arithmetic circuit via pseudorandom generator will show similar lower bound.

Joint work with V. Arvind and S. Srinivasan.