Revision #2 Authors: Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan

Accepted on: 25th April 2008 00:00

Downloads: 2887

Keywords:

Using ideas from automata theory we design a new efficient

(deterministic) identity test for the emph{noncommutative} polynomial

identity testing problem (first introduced and studied by Raz-Shpilka in

2005 and Bogdanov-Wee in 2005). More precisely, given as input a

noncommutative circuit $C(x_1,cdots,x_n)$ computing a polynomial in

$F{x_1,cdots,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 $Cequiv 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 $finF{x_1,cdots,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 1991 and Raz-Shpilka in 2005). 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.

Revision #1 Authors: Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan

Accepted on: 20th March 2008 00:00

Downloads: 3229

Keywords:

Using ideas from automata theory we design a new efficient (deterministic) identity test for the emph{noncommutative} polynomial identity testing problem (first introduced and studied by Raz-Shpilka in 2005 and Bogdanov-Wee in 2005). More precisely, given as input a noncommutative circuit $C(x_1,cdots,x_n)$ computing a polynomial in $F{x_1,cdots,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 $Cequiv 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 $finF{x_1,cdots,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 1991 and Raz-Shpilka in 2005). 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.

TR08-025 Authors: Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan

Publication: 12th March 2008 09:41

Downloads: 2987

Keywords:

Using ideas from automata theory we design a new efficient

(deterministic) identity test for the \emph{noncommutative}

polynomial identity testing problem (first introduced and studied by

Raz-Shpilka in 2005 and Bogdanov-Wee in 2005). More precisely,

given as input a noncommutative

circuit $C(x_1,\cdots,x_n)$ computing a polynomial in

$\F\{x_1,\cdots,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\in\F\{x_1,\cdots,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 1991 and Raz-Shpilka

in 2005). 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.