About

This workshop is about the closely related subjects of random graphs, random manifolds, and random matrices.

Random graph theory and random matrix theory have various applications in theoretical computer science.  Recently there are major new developments in these areas.  An astonishing result by Huang-McKenzie-Yau proves that approximately 69% of regular graphs are Ramanujan via the universality phenomenon in random matrix theory. The polynomial method of Chen-Garza Vargas-Tropp-van Handel dramatically simplifies and strengthens results on norms of polynomials in random permutation matrices (and more generally, on the “strong convergence” phenomenon in free probability). An influential result by Bandeira-Boedihardjo-van Handel established a stronger matrix concentration inequality for certain highly non-commuting random matrices (again relying on concepts in free probability), which played a key role in the recent progress on the matrix Spencer conjecture in discrepancy theory. The workshop will explore these developments and their applications in theoretical computer science.

On the more mathematical side, the study of the spectra of graphs and the study of spectra of manifolds have been intertwined since the early days of the fields. The flow of ideas only increased over time. In the last 20 years, models for random manifolds which are inspired by models for random graphs were introduced. Prominent recent developments include Hide-Magee’s result on high-genus surfaces with nearly optimal spectral gap, relying on the work of Bordenave-Collins on strong convergence; Anantharaman-Monk’s work on the Weil-Petersson model for random surfaces which uses ideas from Friedman’s proof of Alon’s conjecture on random regular graphs; and simpler proofs and new results in both fields arising from the aforementioned advances in strong convergence. The workshop will examine this fruitful analogy between random graphs and manifolds, which is still mysterious and deserves to be explored further.