Deciding whether or not two given finite graphs are isomorphic has for decades been known as one of a small number of natural computational problems with unsettled complexity status within the P/NP theory.
Building on a framework introduced in a seminal 1980 paper by Eugene M. Luks, recent algorithmic progress on this problem has involved an interplay between finite permutation groups, graphs, and algorithmic techniques such as the ``Divide and Conquer'' principle.
The talk will attempt to illustrate some of the components of this work.
No prior knowledge of group theory, graphs, or algorithms will be assumed. |