<p>You can look at <a href="https://www.cc.gatech.edu/~mihail/LINIALexpsurvey.pdf" rel="noreferrer">this survey</a> by Hoory, Linial, and Wigderson [1]. Chapter 9, specifically (p. 508) is on the zigzag product.</p>

<p><code>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</code></p>

<hr>

<p>[1] Hoory, Shlomo, Nathan Linial, and Avi Wigderson. <em>Expander graphs and their applications.</em> Bulletin of the American Mathematical Society 43.4 (2006): 439-561.</p>

CC BY-SA 4.0
2019-07-26T19:44:02.480Z
2019-07-26T19:44:02.480Z
Clement C.
<p>Here are some additional notes: lecture <a href="http://pages.cs.wisc.edu/~dieter/Courses/2006s-CS880/Scribes/06/lecture06.ps" rel="noreferrer">notes</a> by Dieter van Melkebeek , <a href="https://people.eecs.berkeley.edu/~luca/cs359g/lecture17.pdf" rel="noreferrer">notes</a> from Luca Trevisan's course on expanders. </p>

CC BY-SA 4.0
2019-07-27T10:44:19.403Z
2019-07-27T10:44:19.403Z
A.2
<p>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. </p>

CC BY-SA 4.0
2019-07-26T17:21:39.870Z
The expander chapter in Vadhan's pseudorandomness monograph? https://people.seas.harvard.edu/~salil/pseudorandomness/expanders.pdf
Sam McGuire
<cc.complexity-theory><reference-request><expanders>
reference request for construction of expanders
Mr. Cooperman
# reference request for construction of expanders

(Asked by: username_0 on 2019-07-26)

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.

**Tags:** cc.complexity-theory, reference-request, expanders

> **Comments:**
> **username_1**: The expander chapter in Vadhan's pseudorandomness monograph? https://people.seas.harvard.edu/~salil/pseudorandomness/expanders.pdf  

---

## 2 answers

### Answer by username_2 on 2019-07-26. Score: 8

You can look at [this survey](https://www.cc.gatech.edu/~mihail/LINIALexpsurvey.pdf) 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.


---

### Answer by username_3 on 2019-07-27. Score: 5

Here are some additional notes: lecture [notes](http://pages.cs.wisc.edu/~dieter/Courses/2006s-CS880/Scribes/06/lecture06.ps) by Dieter van Melkebeek , [notes](https://people.eecs.berkeley.edu/~luca/cs359g/lecture17.pdf) from Luca Trevisan's course on expanders.


---

