TR14-028 Authors: Vikraman Arvind, S Raja

Publication: 28th February 2014 15:05

Downloads: 2772

Keywords:

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.