Babai’s Updated Results–Graph Isomophism Still Solved in Quasipolynomial Time

Many days overdue on this post but I felt obligated to post this for posterity’s sake (even at woefully so late a time) because the previous post on my blog no longer holds. Laszlo Babai has (since 9 days ago…) posted a fix to his timing analysis so that his graph isomorphism test now once again runs in quasipolynomial time. You can see the announcement here and the updated paper here.

Here are also a short blog post written by Harald Helfgott and his article on Babai’s algorithm for solving GI in quasipolynomial time. The article is currently written in French but it looks like it might be translated into English soon.

Advertisements
This entry was posted in Algorithms, Math and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s