Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture

Abstract

Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an $n\times n$ matrix $M$ and will receive $n$ column-vectors of size $n$, denoted by $v_1,\dots ,v_n$, one by one. After seeing each vector $v_i$, we have to output the product $M{v}_i$ before we can see the next vector. A naive algorithm can solve this problem using $O(n^3)$ time in total, and its running time can be slightly improved to $O(n^3/{\log }^{2}n)$ [Williams SODA'07]. We show that a conjecture that there is no truly subcubic ($O(n^{3-\epsilon })$) time algorithm for this problem can be used to exhibit the underlying polynomial time hardness shared by many dynamic problems. For a number of problems, such as subgraph connectivity, Pagh's problem, $d$-failure connectivity, decremental single-source shortest paths, and decremental transitive closure, this conjecture implies tight hardness results. Thus, proving or disproving this conjecture will be very interesting as it will either imply several tight unconditional lower bounds or break through a common barrier that blocks progress with these problems. This conjecture might also be considered as strong evidence against any further improvement for these problems since refuting it will imply a major breakthrough for combinatorial Boolean matrix multiplication and other long-standing problems if the term "combinatorial algorithms" is interpreted as "non-Strassen-like algorithms" [Ballard et al. SPAA'11]. The conjecture also leads to hardness results for problems that were previously based on diverse problems and conjectures, such as 3SUM, combinatorial Boolean matrix multiplication, triangle detection, and multiphase, thus providing a uniform way to prove polynomial hardness results for dynamic algorithms; some of the new proofs are also simpler or even become trivial. The conjecture also leads to stronger and new, non-trivial, hardness results.

A preliminary version of this paper was presented at the 47th ACM Symposium on Theory of Computing (STOC 2015)

References in corpus (2)

• Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
• Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs

Cited by in corpus (46)

• Faster Dynamic Matrix Inverse for Faster LPs
• A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
• On Fully Dynamic Graph Sparsifiers
• Dynamic Suffix Array with Polylogarithmic Queries and Updates
• Solving Linear Programs in the Current Matrix Multiplication Time
• Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
• Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
• Change Propagation Without Joins
• Conditional Lower Bounds for Space/Time Tradeoffs
• Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
• New Unconditional Hardness Results for Dynamic and Online Problems
• Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
• Fine-Grained Complexity of Regular Path Queries
• Recent Advances in Fully Dynamic Graph Algorithms
• Dynamic Graph Algorithms and Graph Sparsification: New Techniques and Connections
• Input-Dynamic Distributed Algorithms for Communication Networks
• Fully Dynamic Single-Source Reachability in Practice: An Experimental Study
• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
• Conditional Lower Bounds for Variants of Dynamic LIS
• An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications
• Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks
• Near-Optimal Fully Dynamic Densest Subgraph
• Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in $O(1)$ Amortized Update Time
• Stronger 3SUM-Indexing Lower Bounds
• Conditional Lower Bound for Inclusion-Based Points-to Analysis
• Upper and Lower Bounds for Fully Retroactive Graph Problems
• Rewriting with Acyclic Queries: Mind Your Head
• Fine-Grained Complexity and Conditional Hardness for Sparse Graphs
• Decoding Hidden Markov Models Faster Than Viterbi Via Online Matrix-Vector (max, +)-Multiplication
• Faster Dynamic Range Mode
• Dynamic Longest Increasing Subsequence and the Erdös-Szekeres Partitioning Problem
• Faster Randomized Worst-Case Update Time for Dynamic Subgraph Connectivity
• On the complexity of the (approximate) nearest colored node problem
• Cut-Toggling and Cycle-Toggling for Electrical Flow and Other p-Norm Flows
• Random Rank-Based, Hierarchical or Trivial: Which Dynamic Graph Algorithm Performs Best in Practice?
• A Framework for Building Data Structures from Communication Protocols
• Hardness of Dynamic Core and Truss Decompositions
• New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut
• Decremental All-Pairs Shortest Paths in Deterministic Near-Linear Time
• Algorithms and Hardness for Linear Algebra on Geometric Graphs
• A New Deterministic Algorithm for Dynamic Set Cover
• Maintaining Triangle Queries under Updates
• Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs
• Dynamic Data Structures for Interval Coloring
• New Amortized Cell-Probe Lower Bounds for Dynamic Problems
• Exploiting Computation-Friendly Graph Compression Methods