4
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

Here are some additional notes: lecture notes by Dieter van Melkebeek , notes from Luca Trevisan's course on expanders.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.