Posts Tagged ‘algorithms’

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.

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.