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.