论文标题
朝着紧密的界限，以进行光谱稀疏性
Towards Tight Bounds for Spectral Sparsification of Hypergraphs
论文作者
论文摘要
图形的剪切和光谱稀疏具有许多应用，包括例如加速算法，以进行切割和laplacian求解器。这些强大的概念最近已扩展到超图，这些概念更丰富，可能会提供新的应用程序。但是，在超图弹药器大小上的电流边界不如图形的相应边界那样紧。 我们的第一个结果是一种多项式时算法，鉴于具有最大高度尺寸$ r $的$ n $顶点的超图，输出了$ε$ - 光谱的稀疏器，带有$ o^*（nr）$ hyereedges，其中$ o^*$ pundiestes $（ε^{ε^{ - 1}} { - 1} \ log n）^$（1} \ log n）^$（1）这种尺寸的边界改善了以前的两个界限：$ o^*（n^3）$ [soma and yoshida，soda'19]和$ o^*（nr^3）$ [Bansal，Svensson和Trevisan，focs'19]。我们的主要技术工具是一种新的方法，用于证明laplacians二次形式的非线性类似物用于超图扩展器的二次形式。 我们对$（1+ε）$的任何压缩方案的位复杂性进行补充，近似于给定的超图中的所有切割，因此，也要在每个$ε$ cut/specter-sparsifier的位复杂性上。这些下限基于Ruzsa-szemerédi图，即使对于固定常数$ε$，特定的实例化也会在位复杂性上产生$ω（nr）$下限。由于最近的HyperGraph削减了[Chen，Khanna和Nagda，focs'20]的HyperGraph Cut Sparsifiers，这对$ N $中的多毛因子因素很紧张。 最后，对于定向超图，我们提出了一种算法，该算法使用$ o^*（n^2r^3）计算$ε$ spectral Sparsifier，其中$ r $是hyperarc的最大尺寸。对于小$ r $，这比$ o^*（n^3）$改善了[soma和yoshida，soda'19]，并且接近$ω（n^2）$ hyperarcs的微不足道的下限。
Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently been extended to hypergraphs, which are much richer and may offer new applications. However, the current bounds on the size of hypergraph sparsifiers are not as tight as the corresponding bounds for graphs. Our first result is a polynomial-time algorithm that, given a hypergraph on $n$ vertices with maximum hyperedge size $r$, outputs an $ε$-spectral sparsifier with $O^*(nr)$ hyperedges, where $O^*$ suppresses $(ε^{-1} \log n)^{O(1)}$ factors. This size bound improves the two previous bounds: $O^*(n^3)$ [Soma and Yoshida, SODA'19] and $O^*(nr^3)$ [Bansal, Svensson and Trevisan, FOCS'19]. Our main technical tool is a new method for proving concentration of the nonlinear analogue of the quadratic form of the Laplacians for hypergraph expanders. We complement this with lower bounds on the bit complexity of any compression scheme that $(1+ε)$-approximates all the cuts in a given hypergraph, and hence also on the bit complexity of every $ε$-cut/spectral sparsifier. These lower bounds are based on Ruzsa-Szemerédi graphs, and a particular instantiation yields an $Ω(nr)$ lower bound on the bit complexity even for fixed constant $ε$. This is tight up to polylogarithmic factors in $n$, due to recent hypergraph cut sparsifiers of [Chen, Khanna and Nagda, FOCS'20]. Finally, for directed hypergraphs, we present an algorithm that computes an $ε$-spectral sparsifier with $O^*(n^2r^3)$ hyperarcs, where $r$ is the maximum size of a hyperarc. For small $r$, this improves over $O^*(n^3)$ known from [Soma and Yoshida, SODA'19], and is getting close to the trivial lower bound of $Ω(n^2)$ hyperarcs.
