Awesomes Blogs By Friends

Recent Posts
Categories
Top Posts & Pages
Blog Stats
 9,719 hits
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
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
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
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