Derandomizing Matrix Concentration Inequalities from Free Probability @SimonsInstitute
Derandomizing Matrix Concentration Inequalities from Free Probability  @SimonsInstitute
Uploaded October 2026 | Updated November 2026, 3 days ago
Robert Wang (University of Waterloo)
https://simons.berkeley.edu/talks/robert-wang-university-waterloo-2026-10-13
Probabilistic Phenomena on Graphs, Groups, and Manifolds

Recently, sharp matrix concentration inequalities were developed using the theory of free probability. The main observation underlying these results is that certain random matrix models that are "highly non-commutative" are well-approximated by deterministic operators. This phenomenon was dubbed "intrinsic freeness". In this talk, we will show how the intrinsic freeness property can also be used for efficient computation by derandomizing these new concentration inequalities. Using basic tools from free probability, we develop deterministic algorithms to construct matrix outcomes that satisfy the high-probability eigenvalue bounds. As direct consequences, we obtain polynomial time deterministic algorithms for construction of near-Ramanujan expander graphs.
Derandomizing Matrix Concentration Inequalities from Free ProbabilityBinary code rate bounds via classical quantum channelsSpectral Diversity as a Paradigm for Trustworthy AIHallucination Rates in Language GenerationExplicit Almost-Optimal ε-Balanced Codes via Free Expander WalksKikuchi Graphs: A Spectral Method for HypergraphsA survey on PIT for read-once algebraic branching programsNew directions in catalytic derandomizationPolar Codes IFourier quasicrystals from stable polynomials and beyondAlgebraic Geometry and Discrete Periodic OperatorsFinite free information inequalities
Simons Institute for the Theory of Computing |

Derandomizing Matrix Concentration Inequalities from Free Probability

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER