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

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)