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 approach the partially commutative variant of the SDIT and related problems efficiently. The talk is based on joint work with V. Arvind, and Abhranil Chatterjee.
Short Bio:
Partha Mukhopadhyay obtained his PhD from The Institute of Mathematical Sciences (IMSc, 2009), and then he was a postdoctoral fellow at the Israel Institute of Technology. (Technion, 2010). Since then, he is a faculty member at Chennai Mathematical Institute (CMI). His research interest is mainly in the design of algorithms for problems which have algebraic flavour. Outside academics, he enjoys long distance running, table tennis, and painting.
