Hello, and Welcome to Fun with Expanders

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.

6 thoughts on “Hello, and Welcome to Fun with Expanders

  1. Great! 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

  2. Out 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.?

  3. Dear 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.


    Son P. Nguyen

  4. I 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.

  5. Pingback: Mixing Times 6 – Aldous-Broder Algorithm and Cover Times | Eventually Almost Everywhere

  6. I 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s