English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natural analogue of this problem, for which optimal bounds on the sparsifier size are not known, mainly because the hypergraph Laplacian is non-linear, and thus lacks the linear-algebraic structure and tools that have been so effective for graphs. Our main contribution is the first algorithm for constructing <tex>$\epsilon$</tex>-spectral sparsifiers for hypergraphs with <tex>$O^{\ast}(n)$</tex> hyperedges, where <tex>$O^{\ast}$</tex> suppresses <tex>$(\epsilon^{-1}\log n)^{O(1)}$</tex> factors. This bound is independent of the rank <tex>$r$</tex> (maximum cardinality of a hyperedge), and is essentially best possible due to a recent bit complexity lower bound of <tex>$\Omega(nr)$</tex> for hypergraph sparsification. This result is obtained by introducing two new tools. First, we give a new proof of spectral concentration bounds for sparsifiers of graphs; it avoids linear-algebraic methods, replacing e.g. the usual application of the matrix Bernstein inequality and therefore applies to the (non-linear) hypergraph setting. To achieve the result, we design a new sequence of hypergraph-dependent <tex>$\epsilon$</tex>-nets on the unit sphere in <tex>$\mathbb{R}^{n}$</tex>. Second, we extend the weight-assignment technique of Chen, Khanna and Nagda [FOCS&#x0027;20] to the spectral sparsification setting. Surprisingly, the number of spanning trees after the weight assignment can serve as a potential function guiding the reweighting process in the spectral setting.

Spectral Hypergraph Sparsifiers of Nearly Linear Size