ECCC-Report TR19-063https://eccc.weizmann.ac.il/report/2019/063Comments and Revisions published for TR19-063en-usSun, 28 Apr 2019 18:46:25 +0300
Paper TR19-063
| Efficient Black-Box Identity Testing for Free Group Algebra |
Abhranil Chatterjee,
Vikraman Arvind,
Partha Mukhopadhyay,
Rajit Datta
https://eccc.weizmann.ac.il/report/2019/063Hrubeš and Wigderson [HW14] initiated the study of
noncommutative arithmetic circuits with division computing a
noncommutative rational function in the free skew field, and
raised the question of rational identity testing. It is now known
that the problem can be solved in deterministic polynomial time in
the white-box model for noncommutative formulas with
inverses, and in randomized polynomial time in the black-box
model [GGOW16, IQS18, DM18], where the running time is
polynomial in the size of the formula.
The complexity of identity testing of noncommutative rational
functions remains open in general (when the formula size
is not polynomially bounded). We solve the problem for a natural
special case. We consider polynomial expressions in the free group
algebra $\mathbb{F}\langle X, X^{-1}\rangle$ where $X=\{x_1, x_2, \ldots, x_n\}$, a
subclass of rational expressions of inversion height one. Our main
results are the following.
1. Given a degree $d$ expression $f$ in $\mathbb{F}\langle X, X^{-1}\rangle$ as a black-box, we obtain a randomized $\text{poly}(n,d)$ algorithm to check
whether $f$ is an identically zero expression or not. We obtain this
by generalizing the Amitsur-Levitzki theorem [AL50] to
$\mathbb{F}\langle X, X^{-1}\rangle$. This also yields a deterministic identity testing algorithm (and even
an expression reconstruction algorithm) that is polynomial time in
the sparsity of the input expression.
2. Given an expression $f$ in $\mathbb{F}\langle X, X^{-1}\rangle$ of degree at most
$D$, and sparsity $s$, as black-box, we can check whether $f$ is
identically zero or not in randomized $\text{poly}(n,\log s, \log D)$
time.
Sun, 28 Apr 2019 18:46:25 +0300https://eccc.weizmann.ac.il/report/2019/063