Options
Black-Box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial Time
Journal
Leibniz International Proceedings in Informatics, LIPIcs
ISSN
18688969
Date Issued
2022-09-01
Author(s)
Arvind, V.
Chatterjee, Abhranil
Mukhopadhyay, Partha
Abstract
Hrubeš and Wigderson [11] initiated the complexity-theoretic 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 white-box setting, there are deterministic polynomial-time algorithms due to Garg, Gurvits, Oliveira, and Wigderson [10] and Ivanyos, Qiao, and Subrahmanyam [13]. A central open problem in this area is to design an efficient deterministic black-box identity testing algorithm for rational formulas. In this paper, we solve this for the first nested inverse case. More precisely, we obtain a deterministic quasipolynomial-time black-box 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 [19] and properties of cyclic division algebras [15]. En route to the proof, an important step is to embed the hitting set of Forbes and Shpilka for noncommutative formulas [9] inside a cyclic division algebra of small index.
Volume
245
Subjects