Abstract:
The well-known Zig-Zag product and related graph operators, like derandomized squaring, are fundamentally combinatorial in nature. Classical bounds on their behavior often rely on a mix of combinatorics and linear algebra. However, these traditional bounds are not tight. In this talk, we will present a more refined analysis that utilizes the full spectrum of the graph, rather than relying solely on its spectral expansion. This approach produces tight results. Our technique is analytic, diverging from classical methods: for the upper bound, we apply finite free probability, while for the lower bound, we draw on results from analytic combinatorics.
Based on joint works with Itay Cohen, Gal Maor and Yuval Peled.
No prior knowledge is required.
