posted Nov 27, 2012, 3:41 PM by Ariel Gabizon
updated Dec 3, 2012, 3:16 AM
On Monday we finished discussing Reingold's algorithm for ST- connectivity.
The main things we did: Analysis of the Zig-Zag product - section 126.96.36.199 in the monograph.
and the relation between Spectral expansion and Vertex expansion - Theorem 4.6
On Wednesday we discussed eps-biased sets and the basics of discrete Fourier Analysis. We concluded by showing that eps-biased sets fool width-2 ROBPs. There is no reference for this result, but the following paper shows a generalization of it to `read k'-width 2 ROBP's
We discussed graph operations that will be used in Reingold's Algorithm for undirected connectivity. Squaring, Tensoring and the Zig-Zag product (which we continue to discuss next class) See Section 4.3.2 in the monograph.