Chennai Mathematical Institute


Dr. F.C. Kohli Centre of Excellence

Perspectives in Mathematical Sciences

January 10–February 4, 2022

Tuesday, 18 January 2022, 19:30 IST

Saket Saurabh, Institute of Mathematical Sciences (IMSc), Chennai

Title Graph Isomorphism (on structured inputs) (Video Recording)


The Graph Isomorphism (GI) problem is arguably the most widely known problem whose membership in P is unknown, but which is not believed to be NP-hard. While the existence of a polynomial-time algorithm on general graphs is still elusive, the complexity of Graph Isomorphism has been well understood on several classes of graphs, where structural properties of graphs in question have been used to design polynomial-time procedures solving the problem. In this talk we will look at some of these algorithms for Graph Isomorphism through the perspective of contributions of the speaker.

About the speaker

Saket Saurabh photo Saket Saurabh received his PhD in Computer Science (2008), from The Institute of Mathematical Sciences (IMSc), Chennai. Saurabh spent two years (2007-2009) as a Postdoctoral Fellow at University of Bergen, Norway, and is now a professor at IMSc and at the Department of Informatics at the University of Bergen. His main research interests are in graph algorithms, parameterized algorithms and complexity.

He is a SwarnaJayanti Fellow in Mathematical Sciences (2018), Fellow of Indian Academy of Sciences (2020), Academia Europaea (2020), and European Association for Theoretical Computer Science (EATCS, 2021). He received the inaugural ACM India Early Career Researcher Award in 2020, and Shanti Swarup Bhatnagar Prize (SSB) for Science and Technology 2021 (Mathematical Science). He is also the recipient of an ERC starting grant and an ERC Consolidator Grants in parameterized algorithms.