Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR09-026 | 17th February 2009 00:00

Arithmetic Circuit Size, Identity Testing, and Finite Automata

RSS-Feed




TR09-026
Authors: Vikraman Arvind, Pushkar Joglekar
Publication: 22nd March 2009 14:46
Downloads: 1801
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint