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. The first explicit expander construction was given by Margulis in 1973 and its expansion was explicitly determined by Gabber and Galil, 26 FOCSes ago. Although the first proofs used some deep stuff, by STOC '85 Jimbo and Maruoka had made the proof completely elementary. Here's a simple version of the construction: Take the graph on Z_m x Z_m and connect (x,y) to (x+2y,y), (x+2y+1,y), (x,x+2y), (x,x+2y+1). Also put in the reverse edges. The degree is 8 and the second largest eigenvalue is at most 5 sqrt(2) = 7.07 < 8. You're done.
The proof? Three pages of elementary fiddling around. Zig-Zag's proof? A bit of a tricky definition followed by three pages of elementary fiddling around. (If you prefer a more leisurely treatment, both proofs take about five pages in David Xiao's senior thesis.) Zig-Zag is maybe easier to follow if you like linear algebra, Gabber-Galil if you're down with a little of Fourier analysis. The Zig-Zag construction wins out in terms of intuition -- the GG proof has a very clever trick in it that would be hard to come up with on your own. On the other hand, it's not like one should find it baffling that the Gabber-Galil construction might work -- indeed, Jin-Yi Cai shows that pretty much any similar construction on Z_m x Z_m is an expander.
Finally, the Gabber-Galil construction is hands-down better when it comes to explicitness of construction. (It takes a bit of work and thought to show that Zig-Zagging gives you good explicitness.) And GG's extreme explicitness can certainly come in handy -- just ask our old friend Lance Fortnow and former guest blogger Adam Klivans who used it (via a result of Gutfreund and Viola) to show that RL is contained in L with linear advice.
Perhaps a distinction between "explicit" and "generic" is useful? The zig-zag construction is generic - it produces an expander starting from any graph by operating on it in a certain way. Similarly, the Ben Sasson-Sudan work on locally testable codes... As a rule, generic constructions may be more useful than merely explicit ones.
ReplyDeleteRahul.