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

DOI10.1145/2746539.2746609zbMath1321.65067arXiv1511.06773OpenAlexW2153715991MaRDI QIDQ2941485

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

Related Items (45)

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Upper and lower bounds for fully retroactive graph problems ⋮ Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs ⋮ Unnamed Item ⋮ Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases ⋮ Upper and Lower Bounds for Dynamic Data Structures on Strings ⋮ Mind the gap! ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ A combinatorial cut-toggling algorithm for solving Laplacian linear systems ⋮ Deterministic dynamic matching in worst-case update time ⋮ New amortized cell-probe lower bounds for dynamic problems ⋮ Multiplicative auction algorithm for approximate maximum weight bipartite matching ⋮ Range updates and range sum queries on multidimensional points with monoid weights ⋮ Fine-grained complexity lower bounds for problems in computer aided verification ⋮ Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries ⋮ Fine-Grained Complexity of Regular Path Queries ⋮ Lower bounds for (batch) PIR with private preprocessing ⋮ How fast can we play Tetris greedily with rectangular pieces? ⋮ Unnamed Item ⋮ Dynamic data structures for interval coloring ⋮ Rewriting with Acyclic Queries: Mind Your Head ⋮ Unnamed Item ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ An efficient strongly connected components algorithm in the fault tolerant model ⋮ Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time ⋮ Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version) ⋮ Algorithms and conditional lower bounds for planning problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Internal dictionary matching ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Deterministic dynamic matching in \(O(1)\) update time ⋮ Intersection joins under updates ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Counting Triangles under Updates in Worst-Case Optimal Time ⋮ Fine-Grained Complexity Theory (Tutorial) ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Unnamed Item ⋮ Fault-tolerant distance labeling for planar graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication ⋮ Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• 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
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming

This page was built for publication: Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture