标题： 对称马尔可夫链在多重切片上的特征值边界及其应用 显示英文标题

标题： Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications

摘要： 我们考虑在“平衡多切片”上的随机游走，这些“网格”尊重“网格”的“对称性”，并证明了这类游走中的广泛类别是良好的谱扩张器。 （一个网格是由形式为$\mathcal{S}^n$的点组成的集合，其中有限的$\mathcal{S}$，而平衡多切片是包含相等数量的坐标取$\mathcal{S}$中每一个值的子集。 如果从$u = (u_1,\ldots,u_n)$到$v = (v_1,\ldots,v_n)$的概率在同时对$u$和$v$的坐标进行排列时保持不变，则该游走尊重对称性。） 我们的主要定理表明，在一些技术条件下，每种这样的随机游走，其中一步会导致下一个状态上几乎$\mathcal{O}(1)$-wise 独立的分布，条件是前一个状态，满足非平凡的小奇异值界。 我们给出定理在纠错码上的两个应用：(1) 我们给出了多项式和平衡多重切片上的 juntas-sums 的 Ore-DeMillo-Lipton-Schwartz-Zippel 引理的类似结果。 (2) 我们还为$d$-junta-sum 映射提供了一个局部列表校正算法，将任意网格$\mathcal{S}^n$映射到阿贝尔群，对于每个$(\frac{1}{|\mathcal{S}|^{d}} - \varepsilon)$，从接近最优的$\varepsilon > 0$分数的错误中进行校正，其中$d$-junta-sum 是 (任意多个)$d$-juntas 的和(而$d$-junta 是仅依赖于$d$个$n$变量的函数)。 我们的证明是通过探索对称群的表示理论并将其与一些细致的谱分析相结合而获得的。 显示英文摘要

摘要： 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 $\mathcal{S}^n$ for finite $\mathcal{S}$, and a balanced multi-slice is the subset that contains an equal number of coordinates taking every value in $\mathcal{S}$. A walk respects symmetries if the probability of going from $u = (u_1,\ldots,u_n)$ to $v = (v_1,\ldots,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 $\mathcal{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 $\mathcal{S}^n$ to an Abelian group, correcting from a near-optimal $(\frac{1}{|\mathcal{S}|^{d}} - \varepsilon)$ fraction of errors for every $\varepsilon > 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.