  To date, the only way to argue polynomial lower bounds for dynamic algorithms
is via fine-grained complexity arguments. These arguments rely on strong
assumptions about specific problems such as the Strong Exponential Time
Hypothesis (SETH) and the Online Matrix-Vector Multiplication Conjecture (OMv).
While they have led to many exciting discoveries, dynamic algorithms still miss
out some benefits and lessons from the traditional ``coarse-grained'' approach
that relates together classes of problems such as P and NP. In this paper we
initiate the study of coarse-grained complexity theory for dynamic algorithms.
Below are among questions that this theory can answer.
  What if dynamic Orthogonal Vector (OV) is easy in the cell-probe model? A
research program for proving polynomial unconditional lower bounds for dynamic
OV in the cell-probe model is motivated by the fact that many conditional lower
bounds can be shown via reductions from the dynamic OV problem. Since the
cell-probe model is more powerful than word RAM and has historically allowed
smaller upper bounds, it might turn out that dynamic OV is easy in the
cell-probe model, making this research direction infeasible. Our theory implies
that if this is the case, there will be very interesting algorithmic
consequences: If dynamic OV can be maintained in polylogarithmic worst-case
update time in the cell-probe model, then so are several important dynamic
problems such as $k$-edge connectivity, $(1+\epsilon)$-approximate mincut,
$(1+\epsilon)$-approximate matching, planar nearest neighbors, Chan's subset
union and 3-vs-4 diameter. The same conclusion can be made when we replace
dynamic OV by, e.g., subgraph connectivity, single source reachability, Chan's
subset union, and 3-vs-4 diameter.
  Lower bounds for $k$-edge connectivity via dynamic OV? (see the full abstract
in the pdf file).
