2026-08-19T07:21:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21051 2024-09-16T06:02:39Z ddc:004 open_access

Expanderizing Higher Order Random Walks Alev, Vedat Levi Rao, Shravas Higher Order Random Walks Expander Graphs Glauber Dynamics Derandomized Squaring High Dimensional Expansion Spectral Independence Entropic Independence We study a variant of the down-up (also known as the Glauber dynamics) and up-down walks over an n-partite simplicial complex, which we call expanderized higher order random walks - where the sequence of updated coordinates correspond to the sequence of vertices visited by a random walk over an auxiliary expander graph H. When H is the clique with self loops on [n], this random walk reduces to the usual down-up walk and when H is the directed cycle on [n], this random walk reduces to the well-known systematic scan Glauber dynamics. We show that whenever the usual higher order random walks satisfy a log-Sobolev inequality or a Poincaré inequality, the expanderized walks satisfy the same inequalities with a loss of quality related to the two-sided expansion of the auxillary graph H. Our construction can be thought as a higher order random walk generalization of the derandomized squaring algorithm of Rozenman and Vadhan (RANDOM 2005). We study the mixing times of our expanderized walks in two example cases: We show that when initiated with an expander graph our expanderized random walks have mixing time (i) O(n log n) for sampling a uniformly random list colorings of a graph G of maximum degree Δ = O(1) where each vertex has at least (11/6 - ε) Δ and at most O(Δ) colors, (ii) O_h((n log n)/(1 - ‖J‖_op)²) for sampling the Ising model with a PSD interaction matrix J ∈ ℝ^{n×n} satisfying ‖J‖_op ≤ 1 and the external field h ∈ ℝⁿ- here the O(•) notation hides a constant that depends linearly on the largest entry of h. As expander graphs can be very sparse, this decreases the amount of randomness required to simulate the down-up walks by a logarithmic factor. We also prove some simple results which enable us to argue about log-Sobolev constants of higher order random walks and provide a simple and self-contained analysis of local-to-global Φ-entropy contraction in simplicial complexes - giving simpler proofs for many pre-existing results. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vedat Levi Alev and Shravas Rao 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.58 urn:nbn:de:0030-drops-210510 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.58 eng https://creativecommons.org/licenses/by/4.0/legalcode