License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.57
URN: urn:nbn:de:0030-drops-112723
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11272/
Arvind, V. ;
Chatterjee, Abhranil ;
Datta, Rajit ;
Mukhopadhyay, Partha
Efficient Black-Box 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 white-box model [Ankit Garg et al., 2016; Ivanyos et al., 2018]. It can be solved in randomized polynomial time in the black-box 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 black-box, we obtain a randomized poly(n,d) algorithm to check whether f is an identically zero expression or not. The technical contribution is an Amitsur-Levitzki 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 black-box, we can check whether f is identically zero or not in randomized poly(n,log s, log D) time. This yields a randomized polynomial-time 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 Black-Box Identity Testing for Free Group Algebras}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages = {57:1--57:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-125-2},
ISSN = {1868-8969},
year = {2019},
volume = {145},
editor = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11272},
URN = {urn:nbn:de:0030-drops-112723},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.57},
annote = {Keywords: Rational identity testing, Free group algebra, Noncommutative computation, Randomized algorithms}
}
|
Keywords: |
|
Rational identity testing, Free group algebra, Noncommutative computation, Randomized algorithms |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
17.09.2019 |
