Dr. F.C. Kohli Centre of ExcellencePerspectives in Mathematical SciencesJanuary 10–February 4, 2022Tuesday, 18 January 2022, 19:30 ISTSaket Saurabh, Institute of Mathematical Sciences (IMSc), ChennaiTitle Graph Isomorphism (on structured inputs) (Video Recording) Abstract 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
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. |
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.
