Analytic Insights into the Zig-Zag Product and Its Friends - Part I

Explore the advanced analysis of graph operators like the Zig-Zag product and derandomized squaring in this computer science and discrete mathematics seminar. Delve into a refined approach that utilizes the full spectrum of graphs, producing results that align with experimental observations and are proven to be optimal. Learn how finite free probability and analytic combinatorics are applied to achieve upper and lower bounds, respectively. Gain insights into the limitations of traditional combinatorial and linear algebraic methods, and discover how this new analytic technique provides a more accurate understanding of graph behavior. No prior knowledge is required to follow this talk, which is based on joint works with Itay Cohen, Gal Maor, and Yuval Peled, and covers recent research presented at STOC 2023 and FOCS 2024 conferences.

Analytic Insights into the Zig-Zag Product and Its Friends: Part I - Gil Cohen