CS Faculty Talks
Date: Tuesday, 8 October 2024
Time: 02:00 - 02:50 PM
Venue: Seminar Hall
Trading determinism for noncommutativity in Singularity testing
Partha Mukhopadhyay
Chennai Mathematical Institute.
08-10-2024

---

Abstract

Finding an efficient deterministic algorithm for symbolic determinant identity testing (SDIT) is one of the most important problems in com- putational complexity and very little is known about it. Around 2016, two independent research groups solved the noncommutative version of the problem in deterministic polynomial time (Garg-Gurvits-Oliveira- Wigderson 2016, Ivanyos-Qiao-Subrahmanyam 2017) using very differ- ent techniques. In this talk, we will discuss a different algorithm for this problem based on noncommutative polynomial identity testing. Then I will briefly sketch how this new technique is lifted to solve a long standing open problem in algebraic automata theory. The talk is based on joint work with V. Arvind, and Abhranil Chatterjee