Category 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

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

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

Posted in Algorithms, Math | Tagged , , , , | 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

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

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

Posted in Algorithms, Math | Tagged , , , | 1 Comment

Favorite Martin Gardner Puzzles in Honor of 100th Birthday

I remember reading Gardner’s The Colossal Book of Mathematics in middle school. That and Theoni Pappas’s The Joy of Mathematics were the staples of my mathematical education during those years. I was introduced to Conway’s Game of Life, basic knot … Continue reading

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