Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
From MaRDI portal
Publication:2941485
DOI10.1145/2746539.2746609zbMATH Open1321.65067arXiv1511.06773OpenAlexW2153715991MaRDI QIDQ2941485FDOQ2941485
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)
Abstract: Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an matrix and will receive column-vectors of size , denoted by , one by one. After seeing each vector , we have to output the product before we can see the next vector. A naive algorithm can solve this problem using time in total, and its running time can be slightly improved to [Williams SODA'07]. We show that a conjecture that there is no truly subcubic () 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, -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.
Full work available at URL: https://arxiv.org/abs/1511.06773
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
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Shortest-path queries in static networks
- Approximate distance oracles
- On sparse spanners of weighted graphs
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- On approximate distance labels and routing schemes with affine stretch
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Near-Linear Time Construction of Sparse Neighborhood Covers
- Approximate distance oracles with constant query time
- Fast C-K-R partitions of sparse graphs
- Automata, Languages and Programming
- Ramsey partitions and proximity data structures
Cited In (56)
- Distance queries over dynamic interval graphs
- The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
- 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
- Matching triangles and basing hardness on an extremely popular conjecture
- Answering UCQs under updates and in the presence of integrity constraints
- Title not available (Why is that?)
- Fine-Grained Complexity of Regular Path Queries
- Lower bounds for (batch) PIR with private preprocessing
- Subquadratic algorithms for algebraic 3SUM
- Counting Triangles under Updates in Worst-Case Optimal Time
- Upper and lower bounds for fully retroactive graph problems
- 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
- How fast can we play Tetris greedily with rectangular pieces?
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Title not available (Why is that?)
- Mind the gap!
- Fault-tolerant distance labeling for planar graphs
- Fully dynamic maximal matching in \(O(\log n)\) update time (corrected version)
- 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
- The power of vertex sparsifiers in dynamic graph algorithms
- Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases
- Title not available (Why is that?)
- 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
- Deterministic dynamic matching in worst-case update time
- Towards polynomial lower bounds for dynamic problems
- Fine-Grained Complexity Theory (Tutorial)
- Hardness self-amplification: simplified, optimized, and unified
- Sublinear time algorithms and complexity of approximate maximum matching
- Conditional hardness for sensitivity problems
- 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
- Tight cell probe bounds for succinct Boolean matrix-vector multiplication
- New amortized cell-probe lower bounds for dynamic problems
- An efficient strongly connected components algorithm in the fault tolerant model
- Connectivity oracles for graphs subject to vertex failures
- Upper and lower bounds for dynamic data structures on strings
- Intersection joins under updates
- Deterministic dynamic matching in \(O(1)\) update time
- A combinatorial cut-toggling algorithm for solving Laplacian linear systems
- Multiplicative auction algorithm for approximate maximum weight bipartite matching
Uses Software
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)
