ECCC-Report TR14-028https://eccc.weizmann.ac.il/report/2014/028Comments and Revisions published for TR14-028en-usFri, 28 Feb 2014 15:05:25 +0200
Paper TR14-028
| The Complexity of Two Register and Skew Arithmetic Computation |
S Raja,
Vikraman Arvind
https://eccc.weizmann.ac.il/report/2014/028We 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.
Fri, 28 Feb 2014 15:05:25 +0200https://eccc.weizmann.ac.il/report/2014/028