Complexity Theory Problem Strikes Back

The legendary graph isomorphism problem may be harder than a 2015 result seemed to suggest.

The theoretical computer scientist László Babai has retracted a claim that amazed the computer science community when he made it just over a year ago. In November 2015, he announced that he had come up with a “quasi-polynomial” algorithm for graph isomorphism, one of the most famous problems in theoretical computer science. While Babai’s result has not collapsed completely — computer scientists still consider it a breakthrough — its central claim has been found, after a year of close scrutiny, to contain a subtle error. (January 9, 2017, update: Babai announced that he has fixed the error and renewed his claim that his algorithm runs in quasi-polynomial time, adding that he is “working on an updated arXiv posting.”)

“In Laci Babai, you have one of the most legendary and fearsome theoretical computer scientists there ever was, and in graph isomorphism, one of the most legendary and fearsome problems,” wrote Scott Aaronson, a theoretical computer scientist at the University of Texas, Austin, in an email. “A year ago, Laci threw an unbelievable knockout punch at [graph isomorphism], and now the problem itself seems to have gotten off the mat and thrown a counterpunch.”