Archive for the ‘fact’ Category

Online Talks

October 25, 2011

The talks of FOCS 2010 were video recorded and put online (here). The talks of the recent workshop on algorithms in Stanford are also online (here). The lectures of the algorithms course in MIT is video recorded and put online as well (here). This is fascinating. If this trend continues, in the new future, you can “virtually” attend a conference/workshop without having to travel there. Watching a lecture has even a few benefits: you can pause whenever you like, e.g. for a little rest, or to get a cup of tea!

At what times is a mathematician happy?

November 7, 2010

Paul Seymour has an article titled “How the proof of the strong perfect graph conjecture was found?“, which is an informal and rather nice documentary-type article, and gives a high-level description of the process of finding the proof of the strong perfect graph theorem.

In Section 7, “What’s left?”, he writes

Having worked in Berge graphs for three years now, we have developed intuitions and skills that
took a long time to grow, and also a great fondness for the graphs themselves. Unfortunately the
main problem is solved, and there is a cold wind blowing, almost as if it’s time to go and work in a
new area … There was one other really nice question: what about a polynomial time recognition algorithm? Can one decide in polynomial time whether a graph is Berge? Is the question in NP? These were still open … We thought it would last us for another three happy years, but sadly its resistance collapsed after just a couple of months, and Maria and I managed to twist it into an algorithm.

(Bolding was done by me.) My point is that, Seymour was happy as long as there was an interesting problem to work on, and as soon as it is solved, the happiness is gone! While this may seem contradictory to a non-mathematician (who might think that the mathematician becomes happy after he solves a problem), it is SO TRUE. A mathematician has the best feeling in the course of solving the problem, and maybe a little while after solving it, but not any later!

Thomas’ tutorial and CO754 Assignment2

January 20, 2010

I have recently studied Thomas’ lecture notes on tree-decompositions on graphs, which gives the reader an insight into the concepts of tree-decomposition, tree-width etc. It had a understand-through-solving-problems approach that I believe¬† is very nice and instructive:

But the interesting part was that once I saw the problems of the 2nd assignment of approximation algorithms, I found that one of the optional problems is straightforward as the idea was covered in the notes. Specifically, problem 4(b) is easy if you study paragraphs C5-C9 of the notes.