Graph Isomorphism: the History Continues

18 janvier 2016

Anatol Slissenko (LACL)

In November 2015 László Babai (University of Chicago) had claimed that graph isomorphism can be recognized in quasi-polynomial time. It would be a major breakthrough in the complexity of this problem since the beginning of the 80ies. His result has not been yet checked. The algorithm is very complicated (a manuscript of 85 pages is available) and uses non-trivial group theory and previous results, especially those due to E.Luks and L.Babai himself. In the talk I plan to explain the problem, the history of the research on this subject (only the history related to the result of Babai), and maybe try to outline some difficulties surmounted by Babai.