ECCC-Report TR09-026https://eccc.weizmann.ac.il/report/2009/026Comments and Revisions published for TR09-026en-usSun, 22 Mar 2009 14:46:30 +0200
Paper TR09-026
| Arithmetic Circuit Size, Identity Testing, and Finite Automata |
Vikraman Arvind,
Pushkar Joglekar
https://eccc.weizmann.ac.il/report/2009/026 Let $\F\{x_1,x_2,\cdots,x_n\}$ be the noncommutative polynomial
ring over a field $\F$, where the $x_i$'s are free noncommuting
formal variables. Given a finite automaton $\A$ with the $x_i$'s as
alphabet, we can define polynomials $\f( mod A)$ and $\f(div A)$
obtained by natural operations that we call \emph{intersecting} and
\emph{quotienting} the polynomial $f$ by $\A$.
Related to intersection, we also define the \emph{Hadamard product}
$f\circ g$ of two polynomials $f$ and $g$.
In this paper we study the circuit and algebraic branching program
(ABP) complexities of the polynomials $\f( mod A)$, $\f( div A)$,
and
$f\circ g$ in terms of the corresponding complexities of $f$ and $g$
and size of the automaton $\A$. We show upper and lower bound results.
Our results have consequences in new polynomial identity testing
algorithms (and algorithms for its corresponding search version of
finding a nonzero monomial). E.g.\ we show the following:
\begin{itemize}
\item[(a)] A deterministic $\NC^2$ identity test for noncommutative
ABPs over rationals. In fact, we tightly classify the problem as
complete for the logspace counting class $C_=L$.
\item[(b)] Randomized $\NC^2$ algorithms for finding a nonzero
monomial in both noncommutative and commutative ABPs.
\item[(c)] Over monomial algebras $\F\{x_1,\cdots,x_n\}/I$ we
derive an exponential size lower bound for ABPs computing the
Permanent. We also obtain deterministic polynomial identity testing
for ABPs over such algebras.
\end{itemize}
We also study analogous questions in the \emph{commutative} case and
obtain some results. E.g.\ we show over any commutative monomial
algebra $\Q[x_1,\cdots,x_n]/I$ such that the ideal $I$ is generated by
$o(n/\lg n)$ monomials, the Permanent requires exponential size
monotone circuits.
Sun, 22 Mar 2009 14:46:30 +0200https://eccc.weizmann.ac.il/report/2009/026