2010-04-03

Expander Exaggerations

Now don't get me wrong, the Zig-Zag Product is swell, it's Annals of Math-worthy, and it's inspired a lot of recent work, both in expander constructions and elsewhere (e.g., Reingold's SL = L theorem). However, the story I sometimes heard as to why it was cool was that it was the first explicit expander construction that was actually understandable; that you didn't have to know lots of deep number theory to verify the proof; that all other previously known constructions used zaniness like Weil sums, Ramanujan conjectures, Kazhdan constants and whatnot. But as you probably know, this is an exaggeration; it's really not so.

No comments: