C1: Cell probe complexity - a survey

May 23, 2024

• Cell Probe Complexity Model
• Dynamic connectivity Lower Bound for Paths
  • Path Grid
• Reference

The survey [1] is really beautiful and makes a well-known computer scientist.

Cell Probe Complexity Model

The cell probe model can be viewed as a sequence of $cells$, or words, each of which contains $w$-bit field (normally, we assume that $w= \Theta(\log n)$. This model only calculates the cost of an algorithm by counting the number of reads and writes, and all other computation tasks are ignored. Therefore, this model is used to prove a lower bound not an upper bound.

Dynamic connectivity Lower Bound for Paths

$\textbf{Theorem 1}$. Under the cell prove model, the lower bound worst-case cost is $\Omega(\log n)$ per operation.

Path Grid

It is a $\sqrt{n}$ by $\sqrt{n}$ grid. We use $C_0, C_1,\ldots, C_{\sqrt{n}-1}$ to denote the columns of the grid. This grid has a perfect matching. It is easy to see that there are $\sqrt{n}$ disjoint paths across columns. Then path can be coded by the permutations $\pi_1,\ldots,\pi_{\sqrt{n}-1}$ where $\pi_i$ is the permutation of edges that join column $C_i$ and $C_{i+1}$.

We have two operations on the grid.

• UPDATE($i,\pi$). Replace the $i$-th permutation $\pi$ in the grid with permutation $\pi$. It is equal to $\sqrt{n}$ edge deletions/insertions.
• VERIFY_SUM($i,\pi$). Check if $\sum_{j=1}^i \pi_j = \pi_1 \circ \pi_2 \circ \ldots \circ \pi_j= \pi$. It is equivalent to checking if the first $i$ permutations is equal to a single permutation $\pi$ (also $\sqrt{n}$ connectivity queries).

Reference

[1]. Miltersen, Peter Bro. “Cell probe complexity-a survey.” Proceedings of the 19th conference on the foundations of software technology and theoretical computer science, advances in data structures workshop. 1999. [2]. Advanced Data Structures by Prof. Erik Demaine.