Long in the planning, my online course on graph partitioning algorithms, expanders, and random walks, will start next month.

The course page is up for people to sign up. A friend of mine has compared my camera presence to Sheldon Cooper’s in “Fun with Flags,” which is sadly apt, but hopefully the material will speak for itself.

Meanwhile, I will be posting about some material that I have finally understood for the first time: the analysis of the Arora-Rao-Vazirani approximation algorithm, the Cheeger inequality in manifolds, and the use of the Selberg “3/16 theorem” to analyze expander constructions.

If you are not a fan of recorded performances, there will be a live show in Princeton at the end of June.

### Like this:

Like Loading...

*Related*

## 6 comments

Comments feed for this article

March 12, 2013 at 2:56 am

LZGreat! I was waiting for it. Will the lessons be splitted in short videos like those of several courses at coursera? Short videos are handy but I wonder if they are suited for this kind of courses were theorems can have relatively long proofs.

Anyway, if you like flags like Sheldon you’ll appreciate this video: http://www.youtube.com/watch?v=f2Gne3UHKHs

March 14, 2013 at 9:29 am

Varsha DaniOut of curiosity, what does it mean to “sign up” for the course? Is it possible to just drop in occasionally and enjoy your lectures, or is it a commitment to complete all the assigned work etc.?

March 14, 2013 at 11:54 pm

Son P. NguyenDear prof. Trevisan,

I’ve just finished going over your lecture notes from the class last time. However, I can only download up to lecture 18. This time I hope to get the full set and probably a chance to interact with people who like spectral graph theory.

I have a group in Vietnam who’ve already signed up. We enjoy the papers you wrote with Lee, Gharan and other people.

We look forward to your wonderful course.

Sincerely,

Son P. Nguyen

March 15, 2013 at 6:36 pm

lucaI will post a set of videos once a week, corresponding to the content of two in-class lectures. The videos will have variable length, typically I would expect that the each video will be about 15-30 minutes long.

One can “sign up” and not submit homeworks. You will need an account to access the forum, to ask questions and discuss with other students.

And there will be notes for all lectures, including the analysis of ARV, and the approximate counting algorithms.

April 3, 2013 at 6:43 am

Mixing Times 6 – Aldous-Broder Algorithm and Cover Times | Eventually Almost Everywhere[...] Hello, and Welcome to Fun with Expanders (lucatrevisan.wordpress.com) [...]

April 25, 2013 at 7:14 am

Brandon BartonI think your lectures are absolutely wonderful. I have had some pretty horrible experiences with theoretical courses in the past. A “Fun With Flags” quality of lecture would have been a huge improvement. After several years without touching a theory book and getting a little rusty with proofs, I find your course to be incredible motivation for learning theoretical computer science again.

Your lecture notes, on the other hand, were completely beyond my expectations! I wish every professor gave out lecture notes in beautiful LaTeX.

I truly hope this style of course becomes a trend.