Alladi Ramakrishnan Hall

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

Abhranil Chatterjee

IIT Bombay

Hrube\v{s} and Wigderson (2015) initiated the complexity-theoretic study of noncommutative arithmetic formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem which is to decide whether a noncommutative formula with inverses computes zero in the free skew field, equivalently whether there exists a nonzero matrix evaluation for the input formula. In the white-box setting, there are deterministic polynomial-time algorithms due to 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 such formulas. In this talk, I'll present our recent work that solves 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.

This is joint work with V. Arvind (IMSc) and Partha Mukhopadhyay (CMI).

eccc.weizmann.ac.il/report/2022/067/