Theory Seminar: Identity Testing, Isolation and Lower Bounds

Partha Mukhopadhyay (CS, Technion)

Wednesday, 10.06.2009, 15:00

Taub 337

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.

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.