László Babai is one of the world experts on complexity theory, especially related to groups and graphs. He also recently won the 2015 ACM Knuth Prize, for which we congratulate him.
Today we wish to discuss a new result that he has announced that will place graph isomorphism almost in polynomial time.
More exactly László shows that Graph Isomorphism is in Quasipolynomial Time: that is time of the form
for some constant. Polynomial time is the case when
, but any
is a huge improvement over the previous best result.
Luca Trevisan already has made a post on this result, and Scott Aaronson likewise. Luca further promises to be in Chicago next Tuesday when László gives his talk on the result......
Monday, November 09, 2015
November 10, 2015 - likely a big day for computer science
As R.J. Lipton narrates:
Labels:
computer science,
mathematics
Comments by IntenseDebate
Posting anonymously.
November 10, 2015 - likely a big day for computer science
2015-11-09T17:41:00-05:00
Arun
computer science|mathematics|
Subscribe to:
Post Comments (Atom)