标题： 稀疏化每个群上的凯莱图 显示英文标题

标题： Sparsifying Cayley Graphs on Every Group

摘要： 图论中的一个经典结果，由Batson、Spielman和Srivastava（STOC 2009）提出，表明每个图都存在一个$(1 \pm \varepsilon)$割（或谱）稀疏子图，仅保留$O(n / \varepsilon^2)$重加权边。 然而，当将此结果应用于\emph{凯莱图}时，得到的稀疏子图不再一定是Cayley图——它可以是任意的边子集。 因此，最近的一个研究方向，且目前进展甚微，提出了如下问题：对于任何群$G$，该群$G$上的所有Cayley图是否都存在仅保留$\mathrm{polylog}(|G|)/\varepsilon^2$重加权生成元的稀疏子图？ 作为我们的主要贡献，我们肯定地回答了这个问题，提出了此类Cayley图谱稀疏子图存在的证明，以及一种高效寻找它们的算法。 我们的算法甚至可以扩展到\emph{定向的}Cayley图，如果我们只请求割稀疏子图而不是谱稀疏子图的话。 我们还研究了非阿贝尔群上的线性方程的稀疏化。 与阿贝尔情况相反，我们证明对于非阿贝尔值的方程，必须保留超多项式数量的线性方程，才能在任何输入下近似保留满足方程的数量。 结合我们的Cayley图稀疏化结果，这为Cayley图稀疏化和稀疏化线性方程提供了形式上的区别。 显示英文摘要

摘要： A classic result in graph theory, due to Batson, Spielman, and Srivastava (STOC 2009) shows that every graph admits a $(1 \pm \varepsilon)$ cut (or spectral) sparsifier which preserves only $O(n / \varepsilon^2)$ reweighted edges. However, when applying this result to \emph{Cayley graphs}, the resulting sparsifier is no longer necessarily a Cayley graph -- it can be an arbitrary subset of edges. Thus, a recent line of inquiry, and one which has only seen minor progress, asks: for any group $G$, do all Cayley graphs over the group $G$ admit sparsifiers which preserve only $\mathrm{polylog}(|G|)/\varepsilon^2$ many re-weighted generators? As our primary contribution, we answer this question in the affirmative, presenting a proof of the existence of such Cayley graph spectral sparsifiers, along with an efficient algorithm for finding them. Our algorithm even extends to \emph{directed} Cayley graphs, if we instead ask only for cut sparsification instead of spectral sparsification. We additionally study the sparsification of linear equations over non-abelian groups. In contrast to the abelian case, we show that for non-abelian valued equations, super-polynomially many linear equations must be preserved in order to approximately preserve the number of satisfied equations for any input. Together with our Cayley graph sparsification result, this provides a formal separation between Cayley graph sparsification and sparsifying linear equations.