2022/02/11 by V. Arvind, Arvind, V., Abhranil Chatterjee +3
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2202.05693
openalex publication_date 2022/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Hrube vs and Wigderson (2015) initiated the complexity-theoretic study of\nnoncommutative formulas with inverse gates. They introduced the Rational\nIdentity Testing (RIT) problem which is to decide whether a noncommutative\nrational formula computes zero in the free skew field. In the white-box\nsetting, deterministic polynomial-time algorithms are known for this problem\nfollowing the works of Garg, Gurvits, Oliveira, and Wigderson (2016) and\nIvanyos, Qiao, and Subrahmanyam (2018).\n A central open problem in this area is to design efficient deterministic\nblack-box identity testing algorithm for rational formulas. In this paper, we\nsolve this problem for the first nested inverse case. More precisely, we obtain\na deterministic quasipolynomial-time black-box RIT algorithm for noncommutative\nrational formulas of inversion height two via a hitting set construction.\nSeveral new technical ideas are involved in the hitting set construction,\nincluding key concepts from matrix coefficient realization theory\n(Vol vci vc, 2018) and properties of cyclic division algebra (Lam, 2001).\nEn route to the proof, an important step is to embed the hitting set of Forbes\nand Shpilka for noncommutative formulas (2013) inside a cyclic division algebra\nof small index.\n