Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications

We consider random walks on ``balanced multislices'' of any ``grid'' that respects the ``symmetries'' of the grid, and show that a broad class of such walks are good spectral expanders. (A grid is a set of points of the form Sⁿ for finite S, and a balanced multi-slice is the subset that contains an equal number of coordinates taking every value in S. A walk respects symmetries if the probability of going from u = (u₁, , uₙ) to v = (v₁, , vₙ) is invariant under simultaneous permutations of the coordinates of u and v. ) Our main theorem shows that, under some technical conditions, every such walk where a single step leads to an almost O (1) -wise independent distribution on the next state, conditioned on the previous state, satisfies a non-trivially small singular value bound. We give two applications of our theorem to error-correcting codes: (1) We give an analog of the Ore-DeMillo-Lipton-Schwartz-Zippel lemma for polynomials, and junta-sums, over balanced multislices. (2) We also give a local list-correction algorithm for d-junta-sums mapping an arbitrary grid Sⁿ to an Abelian group, correcting from a near-optimal (1|S|^{d} -) fraction of errors for every > 0, where a d-junta-sum is a sum of (arbitrarily many) d-juntas (and a d-junta is a function that depends on only d of the n variables). Our proofs are obtained by exploring the representation theory of the symmetric group and merging it with some careful spectral analysis.