2026-07-24T08:01:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24400 2025-12-12T15:01:30Z ddc:004 open_access

Eigenvalue Bounds for Symmetric Markov Chains on Multislices with Applications Amireddy, Prashanth Behera, Amik Raj Srinivasan, Srikanth Sudan, Madhu Markov Chains Random Walk Multislices Representation Theory of Symmetric Group Local Correction Low-degree Polynomials Polynomial Distance Lemma 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 𝒮ⁿ for finite 𝒮, and a balanced multi-slice is the subset that contains an equal number of coordinates taking every value in 𝒮. A walk respects symmetries if the probability of going from u = (u_1,…,u_n) to v = (v_1,…,v_n) 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 𝒪(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 𝒮ⁿ to an Abelian group, correcting from a near-optimal (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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prashanth Amireddy and Amik Raj Behera and Srikanth Srinivasan and Madhu Sudan 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.34 urn:nbn:de:0030-drops-244004 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.34 eng https://creativecommons.org/licenses/by/4.0/legalcode