Claimed Breakthrough Slays Classic Computing Problem; Encryption Could Be Next

Tom Simonite in MIT Technology Review:

A professor’s claim to have created an algorithm that dramatically simplifies one of theoretical computer science’s most notorious problems has experts preparing to reconsider a long-established truth of their field. It is also seen as a reminder that similar algorithmic breakthroughs are possible that could weaken the tough-to-crack problems at the heart of the cryptography protecting the world’s digital secrets.

In a packed lecture theater on Tuesday and Thursday this week, University of Chicago professor László Babai gave the first two of a series of three lectures describing his new solution to a problem called graph isomorphism. The problem asks a computer to determine whether two different graphs—in the sense of a collection of “nodes” connected into a network, like a social graph—are in fact different representations of the same thing.

Babai’s lectures have caused excitement because graph isomorphism is known as a very challenging problem believed for more than 30 years to be not too far from the very hardest class of problems for computers to solve. If Babai is right, it is in fact much closer to falling into the class of problems that can be solved efficiently by computers, a category known as P (see “What Does ‘P vs. NP’ Mean for the Rest of Us?”).

“This has caught everyone’s imagination because the improvement is so large,” says Richard Lipton, a professor who works on theoretical computer science at Georgia Institute of Technology. “He got it down to a much lower class.” After MIT associate professor Scott Aaronson heard about Babai’s claim, he bloggedthat it could be “the theoretical computer science result of the decade.”

More here.