Ramanujan graphings and correlation decay in local algorithms
From MaRDI portal
Publication:3452726
DOI10.1002/rsa.20562zbMath1325.05159arXiv1305.6784OpenAlexW2070103376MaRDI QIDQ3452726
Balázs Szegedy, Bálint Virág, Agnes Backhausz
Publication date: 13 November 2015
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1305.6784
Related Items
Factor of IID Percolation on Trees ⋮ Independence ratio and random eigenvectors in transitive graphs ⋮ Factor-of-iid balanced orientation of non-amenable graphs ⋮ A factor of i.i.d. with uniform marginals and infinite clusters spanned by equal labels ⋮ Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree ⋮ On the almost eigenvectors of random regular graphs ⋮ There is no going back: properties of the non-backtracking Laplacian ⋮ Correlation Bounds for Distant Parts of Factor of IID Processes ⋮ Zero-temperature Glauber dynamics on the 3-regular tree and the median process ⋮ Spectral measures of factor of i.i.d. processes on vertex-transitive graphs ⋮ Factors of IID on Trees ⋮ A spectral strong approximation theorem for measure-preserving actions ⋮ Mutual information decay for factors of i.i.d. ⋮ Entropy inequalities for factors of IID ⋮ Typicality and entropy of processes on infinite trees ⋮ Kazhdan groups have cost 1
Cites Work
- Perfect matchings as IID factors on non-amenable groups
- The measurable Kesten theorem
- A measurable-group-theoretic solution to von Neumann's problem
- Ramanujan graphs
- Limits of locally-globally convergent graph sequences
- Symmetric Random Walks on Groups
- NON-BACKTRACKING RANDOM WALKS MIX FASTER
- Borel oracles. An analytical approach to constant-time algorithms
- What Can be Computed Locally?
- Random Walks on Infinite Graphs and Groups
- Amenable actions and almost invariant sets
- Generalized Alon--Boppana Theorems and Error-Correcting Codes
