Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-063 | 28th April 2019 18:24

Efficient Black-Box Identity Testing for Free Group Algebra


Authors: Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay
Publication: 28th April 2019 18:46
Downloads: 768


HrubeŇ° 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)$

ISSN 1433-8092 | Imprint