Hardness for Dynamic Problems; Conclusion and Future Research
summary
Shows concrete reductions: maps an orthogonal vectors instance (n vectors in d dimensions) to a dynamic single‑source reachability instance with about n·d nodes and n·d updates, where inserting edges from the source to dimension nodes per query makes s fail to reach a vector iff the vectors are orthogonal, so any amortized m^{0.9} update+query leads to an n^{1.9} OV solver. Builds a similar reduction from three‑OV to dynamic diameter by adding matchings between coordinate copies so diameter >3 exactly matches an orthogonal triple, yielding near‑quadratic and cubic conditional lower bounds under OMv, OV and SETH/APSP conjectures.
AI-written summary · about
chapters (13)
- 0:00Start
- 1:41Dynamic Problems
- 4:23Many Examples
- 16:08APSP Lower Bounds
- 19:19Single Source Reachability
- 25:41Dynamic Diameter
- 34:17Lower bounds with strong guarantees!
- 39:18Triangle Collection
- 40:31Very Plausible Lower Bounds
- 41:01Map of Reductions
- 42:32Theorem: If Matching Triangles is in truly subcubic time, then so is
- 43:02Proof Sketch
- 55:15Fixed Parameter Subquadratic
related talks
19mDeterministic Dynamic Matching In Worst-Case Update Time
23mTowards General and Tight Hardness Results for Graph Problems
31mNear-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems
10mQuery, Communication and Discrepancy
52mFine-Grained Complexity and Algorithm Design for Graph Reachability and Distance Problems
35mSuperlinear Lower Bounds for Multipass Graph Processing
23mA New Connection Between Node and Edge Depth Robust Graphs
19mLook Before, Before You Leap: Online Vector Load Balancing with Few Reassignments