Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-026 | 17th February 2009 00:00

Arithmetic Circuit Size, Identity Testing, and Finite Automata


Authors: Vikraman Arvind, Pushkar Joglekar
Publication: 22nd March 2009 14:46
Downloads: 4007


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)$,
$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:
\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.
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.

ISSN 1433-8092 | Imprint