Archive for the ‘news’ Category

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.

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.

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.

August

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.

June

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.

First Montreal Spring School in Graph Theory

May 13, 2010

I am attending this one-month summer school in Structural Graph Theory, which is held in Montreal. It is a high-level school with world-class speakers, and I am really enjoying it. We have two classes everyday for four weeks, making a total of 40 lectues.

Paul Seymour talks about excluding induced subgraphs, and, in particular, will sketch a proof of the Strong Perfect Graph Theorem, which he (together with Chudnovsky, Robertson and Thomas) has proved in 2001. This was a huge result, with a 150-pages proof. Not only is he a great problem-solver, but also he is a great teacher. I really do enjoy sitting in his class. He is so smart, draws lots of pictures, and always proves what he wants in a bottom-up way; That is, unlike many others who first write a Theorem statement formally and then write the proof, he first describes intuitively why such a Theorem has to be true, and only then writes it down.

Maria Chudnovsky (the picture is a bit old) also talks about excluding induced subgraphs, but her lectures are independent of the Paul’s. She is also smart and a good instructor (she was Paul’s PhD student and must have learnt a lot from him).

Bruce Reed talks about excluding minors from graphs. In particular he talks about Robertson and Seymour’s Graphs Minor Project. He is a great researcher. Sometimes his lectures are confusing for me, in particular when he talks about planar graphs. Fortunately he has now turned to tree decompositions, which I am a little familiar with.

To summarize, I am so glad that I am attending this school. Structural Graph Theory is really nice (though hard to prove new results) and I enjoy sitting in the classes and working on the assignments. It is like I am back in the IMO training camp (7 years ago)! The city of Montreal is also very nice. Here you see a photo I took in the botanical garden, which I went to see on May 8th.

my approximation algorithms talk and some other news

April 8, 2010

  1. Yesterday I had a talk for the “approximation algorithms” course. The title of my talk was “Approximating the Number of Perfect Matchings in Bipartite Graphs” and I presented an algorithm of Jerrum and Sinclair, developed in 1988. I had spent a lot of time (3-4 days) preparing the slides (actually for this talk I learned to use the Beamer package to create LaTeX-based presentations, and the TikZ/PGF package for creating the graphics) and the result was very good, I liked my slides, and I got positive feedback from the audience. The slides can be found here. In a part of the algorithm I described, a Markov chain was used, and to introduce the concept to the audience, I used the intuition of “random walk on a graph” instead of the formal definition. The picture you see above was one of the slides used to illustrate the distribution of a random walker (a happy ghost in this picture) on the vertices of the underlying graph. I was really relieved after the talk since I am not used to present in English.
  2. The paper I posted about two months ago was accepted in Ars Combinatoria. Another paper which I worked on in the same team (when I was an undergrad) was also recently accepted to appear in Graphs and Combinatorics after some revisions, yoohooo !
  3. The Winter 2010 term is almost finished – I have one final exam (integer programming) and I have to submit the final report for approximation algorithms. I spent most of my time on the courses, and I also read a few papers of Nick (my supervisor).
  4. My plan for the next term: I will attend the First Montreal Spring School in Graph Theory in May, and when I return, I will focus on my research (random graphs) and read related stuff (some ideas: The probabilistic methods by Alon-Spencer, Randomized Algorithms by Motwani-Raghavan, Lectures on Random Graphs and Survey on Regular Random graphs by Nick). I won’t take any course but may audit computational geometry from computer science. What a pity I didn’t attend the “Multi-agent Systems” course offered in Winter 2010 in CS.
  5. A graph theory problem: Prove that there exists an integer k, such that for any connected graph G with more than 2 vertices, one can assign a label from {1,2,…,k} to each edge, such that the sum of the labels of edges incident to every vertex defines a proper coloring for the graph. It has been conjectured that k=3 works, and the currently best known bound is k=5. I think it is a cute problem, see here for more info.

Revised “Nowhere-zero Unoriented Flows in Hamiltonian Graphs” submitted

February 2, 2010

This work was done almost two years ago, when I was an undergrad in Sharif. After being rejected two times, the Ars Combinatoria journal accepted to publish it after revisions. The referee have made quite a few comments/suggestions. I was modifying it during the last 12 days. Today the final (revised) version was created, approved by all authors and sent to the corresponding author. If accepted, this would be my first publication. Well done and congratulations!

The PTAS for Euclidean MST

January 29, 2010

The Arora’s PTAS for Euclidean MST is huge. A breakthrough. A great paper full of original ideas. Although it is too complicated for me to understand fully, I can’t help admiring it. I wish I can write one paper like this in my academic life!