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

Seminar list