Posts Tagged ‘courses’

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!

Advertisements

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.

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.

Integer Programming

March 25, 2010

I really don’t like Integer Programming. But I think having the course has had benefits for me:

  1. I figured out that the decision of changing supervisor was a correct one (my former supervisor worked on IP).
  2. I can understand (feel) what one means when she says “I don’t like this course!”
  3. I can evaluate my performance on something that I don’t like but I have to do.

PS – I want to learn beamer for my approximation algorithms presentation. Hoorraay !