16/10/2013 | |
| Covered (part of) the first chapter in the Survey of Hoory, Linial and Wigderson. |
23/10/2013 | |
|
Defined measures related to sparsest cut and expansion of graphs. Showed that if h>0 then even after deleting e<h fraction of edges there is still a large connected component. Started discussing eigenvalues of graphs. |
30/10/2013 | |
|
Started discussing connection between eigenvalues and expansion. Proved that \lambda>0 implies large vertex expansion. Proved the easy direction of (the discrete version of) Cheeger's inequality. |
6/11/2013 | |
|
Finished proving Cheeger's inequality. Proved a lower bound on the second eigenvalue. Briefly discussed Ramanujan graphs. |
13/11/2013 | |
|
Discussed the LPS construction. Proved the Expander Mixing Lemma. Started talking about random walks on graphs. |
20/11/2013 | |
|
Showed error-amplification for BPP using random walks on expanders. Proved the Chernoff bound for walks on expanders. |
27/11/2013 | |
|
Finished the proof of the Chernoff bound. Gave construction of extractors for high min-entropy. |
12/12/2013 | |
|
Analyzed squaring and tensoring of graphs. Introduced the zig-zag product of graphs, and proved the matrix decomposition lemma that will be used for its analysis. |
19/12/13 | |
| Analyzed the zig-zag product of graphs. Used the square, tensor, and zig-zag operations to give a strongly explicit construction of expanders. |
26/12/13 | |
| We saw the Guruswami-Umans-Vadhan construction of a bi-partite unbalanced expander. |
1/1/14 | |
|
We sketched the Ta-Shma-Umans improvement of the GUV construction. |