Awesomes Blogs By Friends

Recent Posts
Categories
Top Posts & Pages
Blog Stats
 10,095 hits
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
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
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…
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
Posted in Algorithms, Math
Tagged algorithms, convexity, linear programming, math, optimization
Leave a comment
Lagrangian Dual Problem and Weak Duality
Lagrangian Dual Problem I left off in my last post on the Lagrangian dual with the observation that we can turn the Lagrangian dual into the dual we are used to seeing as the dual LP, via a simple transformation. … Continue reading
Lagrangian Dual
It’s January again and that means I have a whole month to do, essentially, whatever I want. And part of what I signed up for is the Directed Reading Program organized by the MIT math department. The topic I will … Continue reading