Ramanujan Auditorium

The Graph Isomorphism Story

V. Arvind

IMSc

he 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.