Speaker: Prof László Babai Affiliation: University of Chicago Time: 5:00 pm Monday, 12 March, 2018 Location: Mathematics & Physics Building (PLT1 303-G20) |
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. |