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

We define a natural class of range query problems, and prove that allproblems within this class have the same time complexity (up to polylogarithmicfactors). The equivalence is very general, and even applies to onlinealgorithms. This allows us to obtain new improved algorithms for all of theproblems in the class.  We then focus on the special case of the problems when the queries areoffline and the number of queries is linear. We show that our range queryproblems are runtime-equivalent (up to polylogarithmic factors) to counting foreach edge $e$ in an $m$-edge graph the number of triangles through $e$. Thisnatural triangle problem can be solved using the best known triangle countingalgorithm, running in $O(m^{2\omega/(\omega+1)}) \leq O(m^{1.41})$ time.Moreover, if $\omega=2$, the $O(m^{2\omega/(\omega+1)})$ running time is knownto be tight (within $m^{o(1)}$ factors) under the 3SUM Hypothesis. In thiscase, our equivalence settles the complexity of the range query problems. Ourproblems constitute the first equivalence class with this peculiar running timebound.  To better understand the complexity of these problems, we also provide adeeper insight into the family of triangle problems, in particular showingblack-box reductions between triangle listing and per-edge triangle detectionand counting. As a byproduct of our reductions, we obtain a simple trianglelisting algorithm matching the state-of-the-art for all regimes of the numberof triangles. We also give some not necessarily tight, but still surprisingreductions from variants of matrix products, such as the $(\min,\max)$-product.

Equivalences between triangle and range query problems