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 = (u1, . . ., un) to v = (v1, . . ., vn) 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 (|S| 1/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.