Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems

By Amir Abboud, Virginia Vassilevska Williams. IEEE Annual Symposium on Foundations of Computer Science, 2014

414 citations recorded by the source corpus.

We consider several well-studied problems in dynamic algorithms and prove that sufficient progress on any of them would imply a breakthrough on one of five major open problems in the theory of algorithms: 1) Is the 3SUM problem on n numbers in O(n2-ε) time for some ε > 0? 2) Can one determine the satisfiability of a CNF formula on n variables and poly n clauses in O((2 - ε)npoly n) time for some ε > 0? 3) Is the All Pairs Shortest Paths problem for graphs on n vertices in O(n3-ε) time for some ε > 0? 4) Is there a linear time algorithm that detects whether a given graph contains a triangle? 5) Is there an O(n3-ε) time combinatorial algorithm for n×n Boolean matrix multiplication? The problems we consider include dynamic versions of bipartite perfect matching, bipartite maximum weight matching, single source reachability, single source shortest paths, strong connectivity, subgraph connectivity, diameter approximation and some nongraph problems such as Pagh's problem defined in a recent paper by Patrascu[STOC 2010].

Subfields: Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/de11864170b38297cfa28847e99414529f66c7dc

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Tight Hardness Results for LCS and Other Sequence Similarity Measures (2015, background): “[5], [41]) and recently also for 2015 IEEE 56th Annual Symposium on Foundations of Computer Science”
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false) (2014, background): “…SETH has served as the basis for proving conditional lower bounds for several important computational problems, including k-Dominating Set [PW10], the diameter of sparse graphs [RW13], local alignment [AWW14], dynamic connectivity problems [AW14], and the Frechet distance computation [Bri14].”
Consequences of Faster Alignment of Sequences (2014, methodology): “More recently, the 3-SUM Conjecture has been used in surprising ways to show polynomial lower bounds for purely combinatorial problems in dynamic algorithms [45,2] and Graph algorithms [45,34,54].”
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture (2015, methodology): “For hardness in terms ofm, Abboud and Vassilevska Williams [1] showed that the 3SUM conjecture can rule out algorithms with m4/3−ε preprocessing time, mα− amortized update time and m2/3−α− amortized query time, for any constants 1/6 ≤ α ≤ 1/3 and 0 < < α.”