  We investigate the limits of one of the fundamental ideas in data structures:
fractional cascading. This is an important data structure technique to speed up
repeated searches for the same key in multiple lists and it has numerous
applications. Specifically, the input is a "catalog" graph, $G$, of constant
degree together with a list of values assigned to every vertex of $G$. The goal
is to preprocess the input such that given a connected subgraph $H$ of $G$ and
a single query value $q$, one can find the predecessor of $q$ in every list
that belongs to $\scat$. The classical result by Chazelle and Guibas shows that
in a pointer machine, this can be done in the optimal time of $\O(\log n +
|\scat|)$ where $n$ is the total number of values. However, if insertion and
deletion of values are allowed, then the query time slows down to $\O(\log n +
|\scat| \log\log n)$. If only insertions (or deletions) are allowed, then once
again, an optimal query time can be obtained but by using amortization at
update time.
  We prove a lower bound of $\Omega( \log n \sqrt{\log\log n})$ on the
worst-case query time of dynamic fractional cascading, when queries are paths
of length $O(\log n)$. The lower bound applies both to fully dynamic data
structures with amortized polylogarithmic update time and incremental data
structures with polylogarithmic worst-case update time. As a side, this also
roves that amortization is crucial for obtaining an optimal incremental data
structure.
  This is the first non-trivial pointer machine lower bound for a dynamic data
structure that breaks the $\Omega(\log n)$ barrier. In order to obtain this
result, we develop a number of new ideas and techniques that hopefully can be
useful to obtain additional dynamic lower bounds in the pointer machine model.
