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 boundfor a model of 2-register straight-line programs (SLPs) which is a universal modelof computation (unlike width-2 algebraic branching programs that are not universal [AW11]).
(2) For noncommutative computations, we show that Coppersmith’s 2-register SLPmodel [BOC88], which can efficiently simulate arithmetic formulas in the commu-tative setting, is not universal. However, assuming the underlying noncommutativering has quaternions, Coppersmith’s 2-register model can simulate noncommutativeformulas efficiently.
(3) We consider skew noncommutative arithmetic circuits and show:
(i) An exponential separation between noncommutative monotone circuits andnoncommutative 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 kn(logn).(iii) We give a deterministic (white box) polynomial-time identity testing algorithm for noncommutative skew circuits