Free Probability and Its Applications to TCS

What does it mean for two matrices to be independent, while preserving properties that make “independence” useful? More generally, how should one define independence for random variables in noncommutative settings? Free probability provides a framework for addressing these questions. Beyond its conceptual appeal, it has powerful applications to the analysis of expander graphs, where classical worst-case methods can be overly pessimistic. In this talk, I will introduce the “free” viewpoint and show how it leads to sharp spectral bounds for the zig-zag product and related constructions. I will also discuss how these ideas yield new progress toward constructing the sparsest possible expanders.

Based on joint works with Yuval Peled, Gil Cohen, and Itay Cohen.