Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR14-028 | 27th February 2014 08:10

#### The Complexity of Two Register and Skew Arithmetic Computation

TR14-028
Authors: Vikraman Arvind, S Raja
Publication: 28th February 2014 15:05
Keywords:

Abstract:

We study two register arithmetic computation and skew arithmetic circuits. Our main results are the following:

(1) For commutative computations, we show that an exponential circuit size lower bound
for a model of 2-register straight-line programs (SLPs) which is a universal model
of computation (unlike width-2 algebraic branching programs that are not universal [AW11]).

(2) For noncommutative computations, we show that Coppersmith’s 2-register SLP
model [BOC88], which can efficiently simulate arithmetic formulas in the commu-
tative setting, is not universal. However, assuming the underlying noncommutative
ring has quaternions, Coppersmith’s 2-register model can simulate noncommutative
formulas efficiently.

(3) We consider skew noncommutative arithmetic circuits and show:

(i) An exponential separation between noncommutative monotone circuits and
noncommutative monotone skew circuits.
(ii) We define $k$-regular skew circuits and show that $(k+1)$-regular skew circuits are strictly powerful than $k$-regular skew circuits, where $k\leq \frac{n}{\omega(\log n)}$.
(iii) We give a deterministic (white box) polynomial-time identity testing algorithm for noncommutative skew circuits.

ISSN 1433-8092 | Imprint