The Zig-zag product is a binary operation which takes two graphs, one large and one small, to produce a graph with the size of the large one and the degree of the small one. It was introduced in 2000 and has been used for constructing expanders and extractors as well as proving that symmetric logspace and logspace are equal.
UC Berkeley
Fall 2021
This course explores the role of randomness in computation and pseudorandomness, focusing on the applications in error-correcting codes, expander graphs, randomness extractors, and pseudo-random generators. The course will also address the question of derandomization of small-space computation. Prerequisites are unspecified, but the course content suggests a high level of expertise.
No concepts data
+ 26 more concepts