A new algorithm efficiently solves the graph isomorphism problem, computer scientist László Babai announced November 10 at a Combinatorics and Theoretical Computer Science seminar at the University of Chicago. The problem requires determining whether two separate sets of interconnected points, known as graphs, are linked in the same way even if the graphs look very different. In practice, existing algorithms can do the job in reasonable time, but it was possible that extremely complex graphs would make the problem intractable. Not anymore.
“My first thought was that this was a joke. I checked the month to make sure it wasn’t April,” says Ryan Williams, a Stanford University computer scientist. “It’s a huge jump in our understanding of the problem.” He says the discovery is potentially the most important theoretical computer science advance in more than a decade.