# Popular conjectures imply strong lower bounds for dynamic problems

arXiv: https://arxiv.org/abs/1402.0054 · HTML: https://mlsanity.com/paper/1402.0054/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Feb 2014.

## Built on by (most cited first, 6 of 6)

- [Fundamental Limitations on Subquadratic Alternatives to Transformers](https://mlsanity.com/paper/2410.04271/) (2024)
- [The complexity of non-stationary reinforcement learning](https://mlsanity.com/paper/2307.06877/) (2023)
- [The Structural Complexity of Matrix-Vector Multiplication](https://mlsanity.com/paper/2502.21240/) (2025)
- [Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds](https://mlsanity.com/paper/2307.06723/) (2023)
- [Connectivity Oracles for Predictable Vertex Failures](https://mlsanity.com/paper/2312.08489/) (2023)
- [On the Complexity of the Matching Problem of Regular Expressions with Backreferences](https://mlsanity.com/paper/2605.07289/) (2026)

## Abstract (arXiv)

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 in O((2-ε)n poly 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].