Logarithmic Lower Bounds in the Cell-Probe Model

摘要: We develop a new technique for proving cell-probe lower bounds on dynamic data structures. This enables us to prove an amortized randomized $\Omega(\lg n)$ bound per operation several structural problems $n$ elements, including partial sums, connectivity among disjoint paths (or forest or graph), and other graph (by simple reductions). Such breaks long-standing barrier of n\,/\lg\lg any language membership problem. It also establishes the optimality existing structures, such as Sleator Tarjan's trees. first $\Omega(\log_B in external-memory model without assumptions structure (such comparison model). Our give query-update trade-off curve matched, e.g., by structures graphs. matching upper sums when parameterized word size maximum additive change update.