Random walks on rotating expanders

DOI10.1145/3564246.3585133MaRDI QIDQ6499278

Gil Cohen, Gal Maor

Publication date: 8 May 2024

zbMATH Keywords

random walks on graphsspectral graph theoryexpander graphsinterlacing familiesfinite free probability

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Randomness-efficient sampling within NC\(^{1}\)
• Ramanujan graphs
• The expected eigenvalue distribution of a large regular graph
• The longest path in a random graph
• The Kadison-Singer problem in discrepancy theory.
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Finite free convolutions of polynomials
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• A Combinatorial Construction of Almost-Ramanujan Graphs Using the Zig-Zag Product
• Extensions of Pure States
• Lectures on the Combinatorics of Free Probability
• Expander graphs and their applications
• Undirected connectivity in log-space
• A Chernoff Bound for Random Walks on Expander Graphs
• Eigenvalues and expansion of regular graphs
• Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes
• Explicit, almost optimal, epsilon-balanced codes
• The PCP theorem by gap amplification
• Expander random walks: a Fourier-analytic approach

This page was built for publication: Random walks on rotating expanders