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 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.

Short Bio:
Gil Cohen has been a professor in the Department of Computer Science at Tel Aviv University since 2018. Previously, he was a postdoctoral researcher at Caltech and Princeton University, after graduating from the Weizmann Institute of Science, where he was advised by Ran Raz. His research focuses on pseudorandomness and derandomization, explicit constructions, coding theory (especially algebraic geometry codes, tree codes, and locally decodable codes), and spectral graph theory, often through the lens of free probability theory.