Arvind, V. ;
Chatterjee, Abhranil ;
Mukhopadhyay, Partha
BlackBox Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial Time
Abstract
Hrubeš and Wigderson [Hrubeš and Wigderson, 2015] initiated the complexitytheoretic study of noncommutative formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem which is to decide whether a noncommutative rational formula computes zero in the free skew field. In the whitebox setting, there are deterministic polynomialtime algorithms due to Garg, Gurvits, Oliveira, and Wigderson [Ankit Garg et al., 2016] and Ivanyos, Qiao, and Subrahmanyam [Ivanyos et al., 2018].
A central open problem in this area is to design an efficient deterministic blackbox identity testing algorithm for rational formulas. In this paper, we solve this for the first nested inverse case. More precisely, we obtain a deterministic quasipolynomialtime blackbox RIT algorithm for noncommutative rational formulas of inversion height two via a hitting set construction. Several new technical ideas are involved in the hitting set construction, including concepts from matrix coefficient realization theory [Volčič, 2018] and properties of cyclic division algebras [T.Y. Lam, 2001]. En route to the proof, an important step is to embed the hitting set of Forbes and Shpilka for noncommutative formulas [Michael A. Forbes and Amir Shpilka, 2013] inside a cyclic division algebra of small index.
BibTeX  Entry
@InProceedings{arvind_et_al:LIPIcs.APPROX/RANDOM.2022.23,
author = {Arvind, V. and Chatterjee, Abhranil and Mukhopadhyay, Partha},
title = {{BlackBox Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial Time}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {23:123:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772495},
ISSN = {18688969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17145},
URN = {urn:nbn:de:0030drops171451},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.23},
annote = {Keywords: Rational Identity Testing, Blackbox Derandomization, Cyclic Division Algebra, Matrix coefficient realization theory}
}
15.09.2022
Keywords: 

Rational Identity Testing, Blackbox Derandomization, Cyclic Division Algebra, Matrix coefficient realization theory 
Seminar: 

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

Issue date: 

2022 
Date of publication: 

15.09.2022 