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

In this paper, we develop a new communication model to prove a data structurelower bound for the dynamic interval union problem. The problem is to maintaina multiset of intervals $\mathcal{I}$ over $[0, n]$ with integer coordinates,supporting the following operations:  - insert(a, b): add an interval $[a, b]$ to $\mathcal{I}$, provided that $a$and $b$ are integers in $[0, n]$;  - delete(a, b): delete a (previously inserted) interval $[a, b]$ from$\mathcal{I}$;  - query(): return the total length of the union of all intervals in$\mathcal{I}$.  It is related to the two-dimensional case of Klee's measure problem. We provethat there is a distribution over sequences of operations with $O(n)$insertions and deletions, and $O(n^{0.01})$ queries, for which any datastructure with any constant error probability requires $\Omega(n\log n)$ timein expectation. Interestingly, we use the sparse set disjointness protocol ofH\aa{}stad and Wigderson [ToC'07] to speed up a reduction from a new kind ofnondeterministic communication games, for which we prove lower bounds.  For applications, we prove lower bounds for several dynamic graph problems byreducing them from dynamic interval union.

Cell-probe Lower Bounds for Dynamic Problems via a New Communication Model