Combinatorics Seminar

The Zig-Zag Product and Reingold’s Theorem

Anurag Sahay, University of Rochester

Thursday, February 27th, 2020
11:00 AM - 12:00 PM
Hylan 1106B

In continuation to the previous talk, we prove Reingold’s theorem that undirected graph connectivity is in \(L\) by using the Zig-Zag product and the theory of expander graphs.

Event contact: asahay at ur dot rochester dot edu