Name
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 in \cite{RS05,BW05}). 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 \cite{N91} and Raz-Shpilka in \cite{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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/s00037-010-0299-8 | Computational Complexity |
Keywords | Field | DocType |
deterministic polynomial identity test,black-box polynomial,entire polynomial,time polynomial,commutative polynomial identity testing,new results,sparse noncommutative polynomial identity,input polynomial,polynomial identity testing,identity testing,noncommuting black-box polynomial,polynomial deterministic identity testing,branching program,commutative ring,automata theory | Alternating polynomial,Discrete mathematics,Polynomial identity testing,Invariant polynomial,Combinatorics,Square-free polynomial,Degree of a polynomial,Polynomial remainder theorem,Homogeneous polynomial,Matrix polynomial,Mathematics | Journal |
Volume | Issue | ISSN |
19 | 4 | 1420-8954 |
Citations | PageRank | References |
17 | 0.66 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Arvind | 1 | 52 | 4.34 |
| Partha Mukhopadhyay | 2 | 91 | 12.71 |
| Srikanth Srinivasan | 3 | 132 | 21.31 |