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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The main theme of this paper is using $k$-dimensional generalizations of thecombinatorial Boolean Matrix Multiplication (BMM) hypothesis and theclosely-related Online Matrix Vector Multiplication (OMv) hypothesis to provenew tight conditional lower bounds for dynamic problems.  The combinatorial $k$-Clique hypothesis, which is a standard hypothesis inthe literature, naturally generalizes the combinatorial BMM hypothesis. In thispaper, we prove tight lower bounds for several dynamic problems under thecombinatorial $k$-Clique hypothesis. For instance, we show that:  * The Dynamic Range Mode problem has no combinatorial algorithms with$\mathrm{poly}(n)$ pre-processing time, $O(n^{2/3-\epsilon})$ update time and$O(n^{2/3-\epsilon})$ query time for any $\epsilon > 0$, matching the knownupper bounds for this problem. Previous lower bounds only ruled out algorithmswith $O(n^{1/2-\epsilon})$ update and query time under the OMv hypothesis.  Other examples include tight combinatorial lower bounds for Dynamic SubgraphConnectivity, Dynamic 2D Orthogonal Range Color Counting, Dynamic 2-PatternDocument Retrieval, and Dynamic Range Mode in higher dimensions.  Furthermore, we propose the OuMv$_k$ hypothesis as a natural generalizationof the OMv hypothesis. Under this hypothesis, we prove tight lower bounds forvarious dynamic problems. For instance, we show that:  * The Dynamic Skyline Points Counting problem in $(2k-1)$-dimensional spacehas no algorithm with $\mathrm{poly}(n)$ pre-processing time and$O(n^{1-1/k-\epsilon})$ update and query time for $\epsilon > 0$, even if theupdates are semi-online.  Other examples include tight conditional lower bounds for (semi-online)Dynamic Klee's measure for unit cubes, and high-dimensional generalizations ofErickson's problem and Langerman's problem.

Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv