Wednesday, March 9, 2011

Gaps in my knowledge

If I was starting over with my education... here are some courses I wish I had had when I was a student:

- Probability and random walks, "a la" Yuval Peres
- Spectral graph theory.


  1. If you don't mind filling the gaps in our knowledge with the gaps in yours, what are your favorite applications of spectral methods to graph algorithms ?
    I know there are applications to the search of large cliques (and more generally dense subgraphs), but surely there must be lots of other applications...

  2. You can teach those classes now. Then you'll learn even more than if you had taken those classes when you were a student

  3. Pascal: the Arora-Barak-Steurer slightly subexponential algorithm for unique games is my worry of the day.

    Luca: true. I taught a lecture on half of the Arora-Barak-Steurer paper yesterday, and got to show how confused I was about more or less everything. My nose is barely above the water, and when a factor of n suddenly appears or disappears, or an x becomes 1-x, or there is an extraneous factor of 1/2, I cannot tell whether there is a typo or whether I am overlooking something. Fortunately I get a second chance next week... (and I printed notes from your blog today, just in case they happen to be enlightening!)