# Category Archives: Algorithms

## 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

Posted in Algorithms, Math | Tagged , | Leave a comment

## Babai’s Result: Still a Breakthrough — Gödel’s Lost Letter and P=NP

Even after today’s retraction of quasi-polynomial 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 quasi-polynomial time. Today Laci … Continue reading

Posted in Algorithms, Math | Tagged , | Leave a comment

## Iterated Log Algorithms

The iterated logarithm is the number of times the logarithm function must be applied to a number before the result is at most . A runtime of is almost, very nearly almost constant but not quite as good as constant … Continue reading

## Five motivations for theoretical computer science

Originally posted on Theory, Evolution, and Games Group:
There are some situations, perhaps lucky ones, where it is felt that an activity needs no external motivation or justification.  For the rest, it can be helpful to think of what the…

Posted in Algorithms, Complexity, Math | Tagged , , | Leave a comment

## Strong Duality and Slater’s Theorem

I left off a few days ago with my explanation of Weak Duality. Today, I will continue with the discussion of strong duality, which states . Strong duality does not always hold but for certain types of problems (especially most … Continue reading