Professor László Babai’s algorithm is next big step in conquering isomorphism in graphs

Professor László BabaiOn November 10, 2015, Prof. Babai gave a talk entitled "Graph Isomorphism in Quasipolynomial Time I: The 'Local Certificates Algorithm,’” in which he outlined a new proof showing that the graph isomorphism problem—determining whether two graphs that appear dissimilar are actually identical—can be solved much more quickly than previously thought.

An example of graph isomorphism

As a result of his breakthrough proof, Nature Journal, an international science publication, wrote an article about the talk entitled “Graph-theory breakthrough tantalizes mathematicians,” which outlines the potential significance of Babai’s approach.

According to the article, the proof was “an innovative approach to solving a stubborn, but elementary, question in graph theory — the mathematical study of networks of nodes and their connections — may signal the first major theoretical advance in understanding the problem in more than 30 years.”

Video of the full talk is available here

Professor Babai’s talk was part of a lecture series presented by the Math department.  After video of the talk was circulating, the proof quickly went viral, generating multiple stories and mentions. 

You can read some of the articles about this revolutionary proof here, here and here, as well as in UofC's own Chicago Maroon.