Awesomes Blogs By Friends

Recent Posts
Categories
Top Posts & Pages
Blog Stats
 10,095 hits
Tag Archives: math
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
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
Paper and Puzzle a Day 5
Today marks another paper and another puzzle so let’s get started. Fractional Cascading is a pretty awesome idea for speeding up searches for the same value in multiple sorted lists. Given lists, a naive algorithm would take time because it … Continue reading
Paper and Puzzle a Day 4
Still a pretty early morning post considering the time I got up… First, the paper: Recently came across the following paper, “Pessimal Algorithms and Simplexity Analysis.” This is the first couple of sentences in the paper, and I have to … Continue reading
Paper and Puzzle a Day 3
Early post to an early morning of paper reading. First, the paper: I’ve been reading into the following paper for the past week or so: Parallel Graph Decompositions Using Random Shifts. One of the cool ideas from the paper is … Continue reading