Singularity Testing: From the Non-Commutative to the Commutative World

Instructor : Abhranil Chatterjee Affiliation : IIT Kanpur Abstract : Derandomizing the Polynomial Identity Testing (PIT) remains one of the central open problems in theoretical computer science. An (almost) equivalent formulation of this problem is the singularity testing, which asks whether a given symbolic matrix is invertible. While derandomization in the commutative setting continues to be elusive, the non-commutative version of the problem admits deterministic polynomial-time algorithms [Garg–Gurvits–Oliveira–Wigderson (FOCS, 2016), Ivanyos–Qiao–Subrahmanyam (ITCS, 2017)]. In this talk, I will describe an intermediate model that generalizes both the commutative and non-commutative settings, and present a deterministic polynomial-time algorithm for singularity testing even when some of the variables are allowed to commute. I will conclude by highlighting several consequences and applications of this result. This talk is based on joint work with V. Arvind and Partha Mukhopadhyay. Short Bio : I am an assistant professor in the Department of Computer Science and Engineering at IIT Kanpur, since December 2024. Before joining IIT Kanpur, I was an INSPIRE Faculty at the Indian Statistical Institute, Kolkata, a visiting faculty member at NISER Bhubaneswar, and a Postdoctoral Researcher at IIT Bombay. I earned my PhD in 2022 from The Institute of Mathematical Sciences, Chennai, under the supervision of Professors V. Arvind and Partha Mukhopadhyay. My research interest lies on the theoretical foundations of computer science, with a focus on algebraic complexity theory and the design of algebraic algorithms.