Alladi Ramakrishnan Hall

Efficient Black-Box Identity Testing for Free Group Algebra

Abhranil

Hrubeš and Wigderson initiated the study of noncommutative arithmetic circuits with division (equivalently, inverse) gates that computes 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, where the running time is polynomial in the size of the formula. However, the complexity of identity testing of noncommutative rational functions remains open in general (when the formula size is not polynomially bounded). In this talk, I will talk about this problem for a natural special case where we allow inverse gates only at the bottom-most layer of the circuit. More precisely, we consider polynomial expressions in the free group algebra F (we use F to denote F.) where X={x_1, x_2,..., x_n}, a subclass of rational expressions of inversion height one. The main results are the following. 1. Given a degree d expression f in F as a black-box, we obtain a randomized poly(n,d) algorithm to check whether f is an identically zero expression or not. We obtain this by generalizing the Amitsur-Levitzki theorem to F. 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 F of degree at most D, and sparsity s, as black-box, we can check whether f is identically zero or not in randomized poly(n,log s, log D) time.