Posts Tagged ‘probabilistic method’

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.


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.


July 5, 2010
  1. I have this reading course “Advanced Random Graph Theory” with Nick for which I have to read and solve exercises, and the topics are foreign to me (though fortunately I have the necessary background to read them properly).
  2. I am TA for the course “Linear Optimization” for which I have to grade many assignments weekly, which takes a great amount of time, and I hate grading.
  3. For my research, I am working on various problems about the Cops and Robbers game. The first problem is, what is the cop number of d-regular random graphs? As this has (almost) been resolved for G(n,p), this problem is likely to be solved. The second problem is, what can we say about the game when the robber is faster than the cops? This paper inspired me to think about this problem. And I settled new lower bounds for the maximum cop number of an n-vertex graph when the speed of robber is between 2 and 6. (Hoorray, I am going to publish it!)
  4. I am trying to gain knowledge about various topics which I might like to pursue in my PhD. I am looking for topics which are somewhat more applied than what I am currently doing but abstract enough for me to enjoy! Examples include bioinformatics, multi-agent systems and social networks. I have to talk with friends and read random papers.
  5. I am reading the book A Mathematician’s Apology, by G.H. Hardy. He is a famous mathematician and talks about life and pursuing mathematics as a profession and what should a man do in his life etc. It is a great book and I think will help someone like me who is struggling with himself deciding what to do in life.

a nice probabilistic argument by Alon

April 12, 2010

These days I am reading “Probabilistic Methods for Algorithmic Discrete Mathematics.” Alon‘s probabilistic proofs are usually beautiful. This one (Theorem 6.1) that I saw today was not an exception. It is really simple to understand, but also very elegant. I can’t help admiring it. It is brilliant. That’s the reason that I like the probabilistic method: because it is full of beautiful proofs. I wish I could write a similar proof someday.