TR19-063 Authors: Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

Publication: 28th April 2019 18:46

Downloads: 663

Keywords:

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)$

time.