Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-028 | 27th February 2014 08:10

The Complexity of Two Register and Skew Arithmetic Computation


Authors: Vikraman Arvind, S Raja
Publication: 28th February 2014 15:05
Downloads: 2772


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