The Geomblog

I did an impromptu lunch presentation with my research group on expanders to celebrate the Godel Prize, and in the process dug up some useful reading. There's nothing here that's new to folks familiar with the main results, but if you want a reading list to help with grasping the significance of the results, read on.

• Luca Trevisan's series on expanders and their relation to Cayley graphs (one, two, three, four)
• Terry Tao's summary of expanders inspired by an Avi Wigderson talk.
  
• My note from SODA 2007 on the Alon/Schwartz/Schapira improved analysis of the replacement product.
• Dieter van Melkebeek's course on expanders

There are some aspects of this story that are worth drawing out. First of all, it's actually possible (I think) to get the SL = L result without using the zig zag product directly. In fact, stray comment on a post by Lance suggests as much, and with the new analysis of the replacement product this might be even more likely.

This doesn't mean that the zig-zag product is useless of course. In fact, there's a wonderful 'return to start' story here, which I'll attempt to convey. Essentially, as Luca describes, many early expander constructions proceeded via taking some special non-Abelian group and constructing its Cayley graph, which was then shown to be an expander. The zig-zag product is described "combinatorially" as a construction that takes two graphs and makes a third out of them, and one advantage of this representation is that it gives more explicit expander constructions. But it turned out that at the core of this hides a group operator ! In a certain sense, the zig zag product of the Cayley graph of two groups is the Cayley graph of the semidirect product of the groups ! This is a result of Alon, Lubotsky and Wigderson.

The ACM site isn't updated yet (here's the press release), but Michael M informs us that Vadhan, Reingold and Wigderson just won the Godel prize, (削除) most likely (削除ここまで) for their paper on the zig-zag graph product, (削除) which had a major role in (削除ここまで) and for Reingold's proof that SL = L. These were inspiration for Dinur's combinatorial PCP theorem.

Congratulations !