Popular conjectures imply strong lower bounds for dynamic problems

Understand

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(n^{2-\epsilon})$ time for some $\epsilon>0$? 2.
• Can one determine the satisfiability of a CNF formula on $n$ variables in $O((2-\epsilon)^n poly n)$ time for some $\epsilon>0$? 3.
• Is the All Pairs Shortest Paths problem for graphs on $n$ vertices in $O(n^{3-\epsilon})$ time for some $\epsilon>0$? 4.