Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-067 | 4th May 2022 13:19

Black-box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial-time


Authors: Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay
Publication: 5th May 2022 13:19
Downloads: 344


Hrube\v{s} and Wigderson (2015) 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, deterministic polynomial-time algorithms are known for this problem following the works of Garg, Gurvits, Oliveira, and Wigderson (2016) and Ivanyos, Qiao, and Subrahmanyam (2018).

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 problem 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 key concepts from matrix coefficient realization theory (Vol?i?, 2018) and properties of cyclic division algebra (Lam, 2001). En route to the proof, an important step is to embed the hitting set of Forbes and Shpilka for noncommutative formulas (2013) inside a cyclic division algebra of small index.

ISSN 1433-8092 | Imprint