论文标题
光谱超弹药通过链接
Spectral hypergraph sparsification via chaining
论文作者
论文摘要
在$ n $顶点的超图中，其中$ d $是高度的最大尺寸，其中有一个加权的超格光谱$ \ varepsilon $ -sparsifier，最多$ o（\ varepsilon^{-2}} \ log（d）这改善了Kapralov，Krauthgamer，Tardos和Yoshida（2021），他们实现了$ O（\ Varepsilon^{ - 4} n（\ log n）^3）$，以及BOUND $ O（\ \ varepsilon^{ - varepsilon^{-2} d n \ log n \ log n \ log n \ log n \ log n \ log n \ log n \ log n）$ cern by bansal and bans and bans and and and and s。 Jambulapati，Liu和Sidford（2022）独立获得了相同的稀疏结果。
In a hypergraph on $n$ vertices where $D$ is the maximum size of a hyperedge, there is a weighted hypergraph spectral $\varepsilon$-sparsifier with at most $O(\varepsilon^{-2} \log(D) \cdot n \log n)$ hyperedges. This improves over the bound of Kapralov, Krauthgamer, Tardos and Yoshida (2021) who achieve $O(\varepsilon^{-4} n (\log n)^3)$, as well as the bound $O(\varepsilon^{-2} D^3 n \log n)$ obtained by Bansal, Svensson, and Trevisan (2019). The same sparsification result was obtained independently by Jambulapati, Liu, and Sidford (2022).
