Popular conjectures imply strong lower bounds for dynamic problems

Abstract

We consider several well-studied problems in dynamic algorithms and prove that sufficient progress on any of them would imply a breakthrough on one of five 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}polyn)$ 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 graph contains a triangle? 5. Is there an $O(n^{3-\epsilon })$ time combinatorial algorithm for $n\times n$ Boolean matrix multiplication? The problems we consider include dynamic versions of bipartite perfect matching, bipartite maximum weight matching, single source reachability, single source shortest paths, strong connectivity, subgraph connectivity, diameter approximation and some nongraph problems such as Pagh's problem defined in a recent paper by Patrascu [STOC 2010].

References in corpus (2)

• Polygon Containment and Translational Min-Hausdorff-Distance between Segment Sets are 3SUM-Hard
• Faster all-pairs shortest paths via circuit complexity

Cited by in corpus (18)

• Multivariate Fine-Grained Complexity of Longest Common Subsequence
• Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails
• Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
• Dynamic DFS Tree in Undirected Graphs: breaking the $O(m)$ barrier
• Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms
• Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in $O(1)$ Amortized Update Time
• Losing Weight by Gaining Edges
• On Nondeterministic Derandomization of Freivalds' Algorithm: Consequences, Avenues and Algorithmic Progress
• Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields
• Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning
• Fine-Grained Complexity and Conditional Hardness for Sparse Graphs
• Decremental Single-Source Reachability in Planar Digraphs
• A Note on the Complexity of Computing the Number of Reachable Vertices in a Digraph
• Tight Lower Bounds for the Workflow Satisfiability Problem Based on the Strong Exponential Time Hypothesis
• Decremental SPQR-trees for Planar Graphs
• Simpler Partial Derandomization of PPSZ for $k$-SAT
• Coloring Graphs having Few Colorings over Path Decompositions
• Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures