I'm looking for a good exposition of the explicit constructive proof of the existence of expander graph families due to Reingold Vadhan and Wigderson. Arora/Barak has a chapter on it, but i find it to be full of typos, more serious errors, and other annoying choices (not to knock AB -- I like it generally). I just started reading the original RVW paper, but I was wondering if there are other good sources.
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ The expander chapter in Vadhan's pseudorandomness monograph? people.seas.harvard.edu/~salil/pseudorandomness/expanders.pdf $\endgroup$– Sam McGuireJul 26, 2019 at 17:21
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
You can look at this survey by Hoory, Linial, and Wigderson [1]. Chapter 9, specifically (p. 508) is on the zigzag product.
9.The zig-zag product
9.1. Introduction
9.2. Construction of an expander family using zig-zag
9.3. Definition and analysis of the zig-zag product
9.4. Entropy analysis
9.5. An application to complexity theory: SL=L
[1] Hoory, Shlomo, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society 43.4 (2006): 439-561.
