Awesomes Blogs By Friends

Recent Posts
Categories
Top Posts & Pages
Blog Stats
 9,719 hits
Author Archives: Quanquan Liu
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…) … Continue reading
Babai’s Result: Still a Breakthrough — Gödel’s Lost Letter and P=NP
Even after today’s retraction of quasipolynomial time for graph isomorphism László Babai is famous for many things, and has made many seminal contributions to complexity theory. Last year he claimed that Graph Isomorphism (GI) is in quasipolynomial time. Today Laci … Continue reading
Where has the time gone? (Part 2)
It is once again that time where I bemoan all the months that have passed since my last blog post. True to character, it has again been 8 months! 8 months! I think along these 8 months, I’ve lost some … Continue reading
Where has the Time Gone?
Hello 2016! As WordPress politely informed me today, it’s been 8 months since my last post! 8 months! Where has the time gone? I would say I’m again making a New Year’s resolution to blog more, but it’s no longer … Continue reading
Posted in Uncategorized
1 Comment
Four Weddings And A Puzzle
Originally posted on Gödel's Lost Letter and P=NP:
An unusual voting problem? “Four Weddings” is a reality based TV show that appears in America on the cable channel TLC. Yes a TV show: not a researcher, not…
Posted in Uncategorized
Leave a comment
Paper and Puzzle a Day 8
Again, I’ve been slightly lax on posting a puzzle and paper a day. Here I am picking up the slack once again. First, a paper. I’ve been reading up on cacheoblivious algorithms recently. Cacheoblivious algorithms are optimal algorithms that do … Continue reading
Paper and Puzzle a Day 7
I’ve been reading up more about hinged dissections and came across a shorter paper than the one I mentioned in my previous post. This paper proves that hinged dissections are PSPACEhard using a reduction from NCL with some neat gadgets. … Continue reading