Please join us On Dec 9th at 10am via Zoom where Abhranil Chatterjee (IIT Kanpur) will give a talk, “Approximating Transcendence Degree in Medium Characteristic”.
https://illinois.zoom.us/j/84700567676?pwd=SG96MlRZT3M0N0paTGFYeEljL2hhUT09
Please see their abstract below:
Abstract: Rational Identity Testing (RIT) is the decision problem of determining whether or not a noncommutative rational formula (formula with addition, multiplication and inverse) has a nonzero matrix evaluation (of any dimension). It admits a deterministic polynomial-time white-box algorithm [Garg, Gurvits, Oliveira, and Wigderson (2016); Ivanyos, Qiao, Subrahmanyam (2018); Hamada and Hirai (2021)], and a randomized polynomial-time algorithm [Derksen and Makam (2017)] in the black-box setting. Indeed, a randomized NC algorithm for RIT in the white-box setting follows from the result of Derksen and Makam (2017).
Designing an efficient deterministic black-box algorithm for RIT and understanding the parallel complexity of RIT are major open problems in this area. Despite being open since the work of Garg, Gurvits, Oliveira, and Wigderson (2016), these questions have seen limited progress.
In this talk, I'll present our recent work where we significantly improve the black-box complexity of this problem and obtain the first quasipolynomial-size hitting set for all rational formulas of polynomial size. Our construction also yields the first deterministic quasi-NC upper bound for RIT in the white-box setting.
Joint work with V. Arvind (IMSc) and Partha Mukhopadhyay (CMI). STOC 2024, https://urldefense.com/v3/__https://eccc.weizmann.ac.il/report/2023/147/__;!!DZ3fjg!8x2sdf1RNLjv--MZL9l1n64nlNyrfrWAP25HK7lDSiAmBEdahRUn7JaB_297zkf67lxmJBkuhhG9DfK9O3BpZnI$ .