Trading determinism for noncommutativity in Singularity testing

Abstract

Finding an efficient deterministic algorithm for symbolic determinant identity testing (SDIT) is one of the most important problems in computational 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 different 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.

Venue: H104