The motivation for this paper is to study the complexity of constant-width arithmetic circuits. Our main results are the following. 1. For every k > 1, we provide an explicit polynomial that can be computed by a linear-sized monotone circuit of width 2k but has no subexponential-sized monotone circuit of ... more >>>

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 ... more >>>