The Graph Isomorphism Story by Prof. V. Arvind

The Graph Isomorphism problem is the algorithmic problem of checking whether two graphs are isomorphic (i.e. checking if they are structurally the same) has been studied since the 1960's. While the problem has many application domains, it has been of much interest in theoretical computer science because it is one of the few natural problems that is neither classified as NP-complete nor has a polynomial-time algorithm. Over the last six decades, research on Graph Isomorphism has grown alongside the development of the field of computational complexity, and its story of symmetry and complexity is interwoven with several concepts in computational complexity. In this talk we will present different aspects of the Graph Isomorphism problem and touch upon its interconnections with a range of ideas, including some recent applications in machine learning.