Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture

DOI10.1145/2746539.2746609MaRDI QIDQ2941485zbMATH OpenOpenAlexFDO

Authors Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak, Monika R. Henzinger

Publication date 21 August 2015

Published in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.06773

zbMATH Keywords

lower boundsdynamic graph algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an $nimesn$ matrix $M$ and will receive $n$ column-vectors of size $n$, denoted by $v_1,ldots,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/lo{g}^{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.

Recommendations

• Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases
• Faster Online Matrix-Vector Multiplication
• Towards polynomial lower bounds for dynamic problems
• New amortized cell-probe lower bounds for dynamic problems
• Matching triangles and basing hardness on an extremely popular conjecture

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(56)

• A new deterministic algorithm for fully dynamic all-pairs shortest paths
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• Deterministic incremental APSP with polylogarithmic update time and stretch
• Distance queries over dynamic interval graphs
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
• Intersection joins under updates
• How fast can we play Tetris greedily with rectangular pieces?
• scientific article; zbMATH DE number 7378710 (Why is no real title available?)
• Fully dynamic maximal matching in \(O(\log n)\) update time (corrected version)
• Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
• Upper and lower bounds for fully retroactive graph problems
• Deterministic dynamic matching in \(O(1)\) update time
• Towards polynomial lower bounds for dynamic problems
• Deterministic dynamic matching in worst-case update time
• Internal dictionary matching
• Algorithms and conditional lower bounds for planning problems
• Hardness self-amplification: simplified, optimized, and unified
• Sublinear time algorithms and complexity of approximate maximum matching
• scientific article; zbMATH DE number 7651196 (Why is no real title available?)
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Fine-grained complexity lower bounds for problems in computer aided verification
• The power of vertex sparsifiers in dynamic graph algorithms
• Elastic-Degenerate String Matching via Fast Matrix Multiplication
• Dynamic data structures for interval coloring
• A combinatorial cut-toggling algorithm for solving Laplacian linear systems
• Nearly optimal separation between partially and fully retroactive data structures
• New amortized cell-probe lower bounds for dynamic problems
• Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
• Rewriting with Acyclic Queries: Mind Your Head
• Matching triangles and basing hardness on an extremely popular conjecture
• Approximating all-pair bounded-leg shortest path and APSP-AF in truly-subcubic time
• An efficient strongly connected components algorithm in the fault tolerant model
• Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
• Fine-Grained Complexity Theory (Tutorial)
• Fooling views: a new lower bound technique for distributed computations under congestion
• Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases
• Conditional hardness for sensitivity problems
• Answering UCQs under updates and in the presence of integrity constraints
• Decremental strongly connected components and single-source reachability in near-linear time
• Range updates and range sum queries on multidimensional points with monoid weights
• Connectivity oracles for graphs subject to vertex failures
• Fine-Grained Complexity of Regular Path Queries
• Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model
• Lower bounds for (batch) PIR with private preprocessing
• scientific article; zbMATH DE number 7561506 (Why is no real title available?)
• On the hardness of approximate and exact (bichromatic) maximum inner product
• Multiplicative auction algorithm for approximate maximum weight bipartite matching
• Towards hardness of approximation for polynomial time problems
• Mind the gap!
• Subquadratic algorithms for algebraic 3SUM
• Upper and lower bounds for dynamic data structures on strings
• Even faster elastic-degenerate string matching via fast matrix multiplication
• Tight cell probe bounds for succinct Boolean matrix-vector multiplication
• Counting Triangles under Updates in Worst-Case Optimal Time
• Fault-tolerant distance labeling for planar graphs

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941485)