Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR08-025 | 25th April 2008 00:00

New results on Noncommutative and Commutative Polynomial Identity Testing Revision of: TR08-025

RSS-Feed

Abstract:

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 to TR08-025 | 20th March 2008 00:00

New results on Noncommutative and Commutative Polynomial Identity Testing


Abstract:

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.


Paper:

TR08-025 | 3rd January 2008 00:00

New results on Noncommutative and Commutative Polynomial Identity Testing


Abstract:

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.



ISSN 1433-8092 | Imprint