Arvind, V. ;
Chatterjee, Abhranil ;
Datta, Rajit ;
Mukhopadhyay, Partha
Efficient BlackBox Identity Testing for Free Group Algebras
Abstract
Hrubes and Wigderson [Pavel Hrubes and Avi Wigderson, 2014] 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. For noncommutative formulas with inverses the problem can be solved in deterministic polynomial time in the whitebox model [Ankit Garg et al., 2016; Ivanyos et al., 2018]. It can be solved in randomized polynomial time in the blackbox model [Harm Derksen and Visu Makam, 2017], where the running time is polynomial in the size of the formula. The complexity of identity testing of noncommutative rational functions, in general, remains open for noncommutative circuits with inverses.
We solve the problem for a natural special case. We consider expressions in the free group algebra F(X,X^{1}) where X={x_1, x_2, ..., x_n}. Our main results are the following.
1) Given a degree d expression f in F(X,X^{1}) as a blackbox, we obtain a randomized poly(n,d) algorithm to check whether f is an identically zero expression or not. The technical contribution is an AmitsurLevitzki type theorem [A. S. Amitsur and J. Levitzki, 1950] for F(X, X^{1}). 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(X,X^{1}) of degree D and sparsity s, as blackbox, we can check whether f is identically zero or not in randomized poly(n,log s, log D) time. This yields a randomized polynomialtime algorithm when D and s are exponential in n.
BibTeX  Entry
@InProceedings{arvind_et_al:LIPIcs:2019:11272,
author = {V. Arvind and Abhranil Chatterjee and Rajit Datta and Partha Mukhopadhyay},
title = {{Efficient BlackBox Identity Testing for Free Group Algebras}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {57:157:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771252},
ISSN = {18688969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11272},
URN = {urn:nbn:de:0030drops112723},
doi = {10.4230/LIPIcs.APPROXRANDOM.2019.57},
annote = {Keywords: Rational identity testing, Free group algebra, Noncommutative computation, Randomized algorithms}
}
17.09.2019
Keywords: 

Rational identity testing, Free group algebra, Noncommutative computation, Randomized algorithms 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Issue date: 

2019 
Date of publication: 

17.09.2019 