Computer Science/Discrete Mathematics Seminar II
Analytic Insights into the Zig-Zag Product and Its Friends: Part II
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 and frequently fail to align with experimental results.
In these talks, 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 results that both match experimental observations and, in a sense, are proved to be optimal. 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.
Relevant papers:
- Random Walks on Rotating Expanders (STOC 2023)
- Tight Bounds for the Zig-Zag Product (FOCS 2024)
- Derandomized Squaring: An Analytic Insight into Its True Behavior (manuscript)