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/

Zendy Plus

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

Zendy Tools

Zendy Open

Spanners, emulators, and approximate distance oracles can be viewed as lossycompression schemes that represent an unweighted graph metric in small space,say $\tilde{O}(n^{1+\delta})$ bits. There is an inherent tradeoff between thesparsity parameter $\delta$ and the stretch function $f$ of the compressionscheme, but the qualitative nature of this tradeoff has remained a persistentopen problem.  In this paper we show that the recent additive spanner lower bound of Abboudand Bodwin is just the first step in a hierarchy of lower bounds that fullycharacterize the asymptotic behavior of the optimal stretch function $f$ as afunction of $\delta \in (0,1/3)$. Specifically, for any integer $k\ge 2$, anycompression scheme with size $O(n^{1+\frac{1}{2^k-1} - \epsilon})$ has asublinear additive stretch function $f$: $$f(d) = d +\Omega(d^{1-\frac{1}{k}}).$$ This lower bound matches Thorup and Zwick's (2006)construction of sublinear additive emulators. It also shows that Elkin andPeleg's $(1+\epsilon,\beta)$-spanners have an essentially optimal tradeoffbetween $\delta,\epsilon,$ and $\beta$, and that the sublinear additivespanners of Pettie (2009) and Chechik (2013) are not too far from optimal.  To complement these lower bounds we present a new construction of$(1+\epsilon, O(k/\epsilon)^{k-1})$-spanners with size $O((k/\epsilon)^{h_k}kn^{1+\frac{1}{2^{k+1}-1}})$, where $h_k < 3/4$. This size bound improves onthe spanners of Elkin and Peleg (2004), Thorup and Zwick (2006), and Pettie(2009). According to our lower bounds neither the size nor stretch function canbe substantially improved.

A Hierarchy of Lower Bounds for Sublinear Additive Spanners