Stories
Slash Boxes
Comments

SoylentNews is people

posted by on Wednesday January 11 2017, @05:03AM   Printer-friendly
from the quasi-correct-algorithm dept.

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.

[...] The graph isomorphism problem asks for an algorithm that can spot whether two graphs — networks of nodes and edges — are the same graph in disguise. For decades, this problem has occupied a special status in computer science as one of just a few naturally occurring problems whose difficulty level is hard to pin down.

[...] Babai, a professor at the University of Chicago, had presented in late 2015 what he said was a "quasi-polynomial" algorithm for graph isomorphism. His work appeared to place the problem, if not firmly in the easy zone, then at least in its suburbs. But on January 4 he announced that while his algorithm still works (with some small tweaks) and has now been carefully checked by other computer scientists, it doesn't run as fast as he had thought. It is "sub-exponential," which moves the problem back into the suburbs of the hard zone.

Babai's algorithm is, nevertheless, significantly faster than the previous best algorithm for graph isomorphism, which had held its title unchallenged for more than 30 years. "It's still a massive improvement over the previous state of the art," said Aaronson by email. Computer scientists conversant in Babai's approach will presumably try to figure out whether further improvements can be milked from it, Aaronson predicted.

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."

-- submitted from IRC


Original Submission

 
This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
  • (Score: 2) by takyon on Wednesday January 11 2017, @08:08PM

    by takyon (881) <reversethis-{gro ... s} {ta} {noykat}> on Wednesday January 11 2017, @08:08PM (#452668) Journal

    Whaddaya mean, review? If the proof is gigabytes in size, it has to be reviewed by a computer that doesn't care how many revisions are fed in.

    That's what we're getting at, right? Math that is too glyphy for humans to parse. Babai's proof is short by comparison.

    --
    [SIG] 10/28/2017: Soylent Upgrade v14 [soylentnews.org]
    Starting Score:    1  point
    Karma-Bonus Modifier   +1  

    Total Score:   2