#### 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/

Done