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

We consider several well-studied problems in dynamic algorithms and provethat sufficient progress on any of them would imply a breakthrough on one offive major open problems in the theory of algorithms:  1. Is the 3SUM problem on $n$ numbers in $O(n^{2-\epsilon})$ time for some$\epsilon>0$?  2. Can one determine the satisfiability of a CNF formula on $n$ variables in$O((2-\epsilon)^n poly n)$ time for some $\epsilon>0$?  3. Is the All Pairs Shortest Paths problem for graphs on $n$ vertices in$O(n^{3-\epsilon})$ time for some $\epsilon>0$?  4. Is there a linear time algorithm that detects whether a given graphcontains a triangle?  5. Is there an $O(n^{3-\epsilon})$ time combinatorial algorithm for $n\timesn$ Boolean matrix multiplication?  The problems we consider include dynamic versions of bipartite perfectmatching, bipartite maximum weight matching, single source reachability, singlesource shortest paths, strong connectivity, subgraph connectivity, diameterapproximation and some nongraph problems such as Pagh's problem defined in arecent paper by Patrascu [STOC 2010].

Popular conjectures imply strong lower bounds for dynamic problems