TR09-026 Authors: Vikraman Arvind, Pushkar Joglekar

Publication: 22nd March 2009 14:46

Downloads: 1801

Keywords:

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.