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!


MIT’s course on algorithms, video lectures online

October 20, 2011

There is a course offered this term in MIT, called Algorithms for Planar Graphs and Beyond. It sounds very interesting. The lectures are recorded, and their video files are available here. I will try to watch them.

Erik Demaine’s talk in Toronto

October 19, 2011

Last week I went to Toronto to attend Erik Demaine’s talk in the FIELDS institute, which was fantastic. He had three talks in consecutive days, and I attended the first one only, titled Algorithms Meet Art, Puzzles, and Magic. He talked about his background, that he liked to design/solve puzzles from childhood, that he travelled a lot in North America when he was a kid, and that he fell in love with algorithms because he found a lot of creativity in this field. He said mathematics and art have strong relationships, and that “they are just two ways of looking at the same thing!” He also said a sentence that I really liked: “Mathematics is a kind of art, since, a mathematician does not only want to prove something; he wants to give a beautiful proof.” His slides were alternatively about math and art. He talked a lot about origami, the art of creating things by folding papers, in some slides he talked about proving mathematical results about the structure and complexity of things that can be created by origami, and whether it is possible to “reverse-engineer” and build a 2D-pattern whose folding yields a given 3D-shape. In other slides, he just showed various interesting examples of what can be done by origami and also beautiful works of his father, a glassblower.

Erik Demaine was born in Halifax in 1981, received his PhD in Computer Science from UWaterloo when he was 20 years old and immediately joined the MIT faculty, where he is now. His PhD thesis was titled “Folding and Unfolding.” He said when he was a grad student, people used to tell him to work on something “serious” if he wants to get a job; but he didn’t listen to them! He is very active and has 296 co-authors.

Time for computer science to grow up

March 2, 2011

“We end up living in a deadline-driven world, submitting a paper when we reach an appropriate conference deadline instead of when the research has been properly fleshed out. Many also just publish “least-publishable units,” doing just enough to get accepted into a conference.”

from: Time for computer science to grow up, Lance Fortnow, Communications of the ACM, 2009

New Constructive Aspects of the Lovász Local Lemma

December 13, 2010

Lovász Local Lemma is a strong probabilistic tool mainly used to prove results about existence of certain discrete structures. Last year R. Moser and G. Tardos presented an algorithm to actually construct those discrete structures. Their proof was really elegant. However, their analysis don’t always provide a polynomial bound for the running time. The authors of this paper, presented in this FOCS, extend their work by showing that the Moser-Tardos algorithm can indeed be altered a bit to give efficient Monte Carlo algorithms in many cases. More info can be found in this post. I enjoyed reading the paper and talked about it in the CombOpt reading group last Tuesday. By the way, the FOCS’10 talks are available online and you can watch the original presentation.

Dijkstra’s 3 Golden Rules for Successful Research

November 13, 2010

1- Raise your quality standards as high as you can live with, avoid wasting your time on routine problems, and always try to work as closely as possible at the boundary of your abilities. Do this, because it is the only way of discovering how that boundary should be moved forward.
2- We all like our work to be socially relevant and scientifically sound. If we can find a topic satisfying both desires, we are lucky; if the two targets are in conflict with each other, let the requirement of scientific soundness prevail.
3- Never tackle a problem of which you can be pretty sure that (now or in the near future) it will be tackled by others who are, in relation to that problem, at least as competent and well-equipped as you.
Source (with some explanations):

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!

My first solo publication, in Discrete Mathematics

October 31, 2010

My BSc project was a survey on Cops and Robber game. I also studied the capture time of Cartesian product of trees, and in Nowrooz holidays (March 2009) I proved that the 2-capture time of a Cartesian product of two trees is half its diameter, and the 2-capture time of an mxn grid is (m+n-2)/2. I submitted my work in January 2010 to Discrete Mathematics and it was accepted in October 2010. This is my first solo publication, it is in a well-known journal, so I am happy 🙂

The manuscript can be found here and the online published version can be found here.

The story of my paper with Noga Alon

October 15, 2010

Well, in one of our meetings in August, Nick (my supervisor) told me that Noga Alon will visit UWaterloo in a few weeks, and I can give him a quick glimpse of my work on Cops and Robber game, and I said Ok, happy to know that I’ll meet him. He came in September and gave a talk in Tutte’s seminar. Next day Nick arranged a meeting in his office and I told Noga my work. He seemed interested, and proposed an idea that if correct, would’ve extended my result. With Nick’s help I worked on the idea for a week or two, and yeaaah … it worked! I was so excited, sent the proof to Nick, and he verified its correctness. Then I contacted Noga and asked if he’d like to be a coauthor, and he confirmed. He made a bunch of corrections and we submitted it. It’s a short paper however (7 pages).

Oh boy, if you’d told me an year ago that just an year after coming to Canada I’ll write a paper with Noga Alon, I would’ve considered it as a joke. But it really happened! Thank you God!

Some technical details: There was a recent preprint by Frieze et al., where they had considered the variation of Cops and Robber where the robber has speed s>1. For every s they had given a lower bound for the maximum cop number of a graph with n vertices in that variation. In summer I had worked on this problem and improved their bound for s<7 (here). I proved the cop number of an n-vertex graph can be as large as n^{s/s+1} when s=2,4. My proof uses regular graphs with large girth, which are called cages. I had also conjectured that this lower bound holds for larger values of s as well. There is an old conjecture of Bollobas about cages that implies my conjecture. Noga told me about regular graphs that don’t have large girths, but for every two close vertices, there are a constant number of shortest paths connected them. These graphs are enough for my proof, and their number of vertices are exactly what I wanted. Hoorraay.


August 25, 2010
  1. The reading course (on random graphs) I had in summer with Nick (my supervisor) has finished, and it was really good: I was introduced to the area of randomized structures (esp. graphs) and processes and solved a few problems. I also became comfortable with asymptotic notations and little/big Oh’s are not scary anymore!
  2. My research is progressing well: I have proved a bunch of small results on Cops and Robbers. First, I found a 3-approximation algorithm for calculating the cop number of an interval graph, assuming the robber has infinite speed. Second, I proved that the cop number of a random regular graph is a.a.s O(n^0.81) if d = n^o(1).
  3. These days I am reading The Probabilistic Method by Alon and Spencer. The method is quite nice, usually results in beautiful proofs, and the book is really well-written. I am reading one chapter per day in order to finish it before the new term.
  4. Next term I am going to take Algorithmic Game Theory and a bioinformatics course from CS department. I am already excited about them. It is cool that so many good courses (with a broad range) are offered in UWaterloo.