\( \newcommand\sd{{\mathtt{sd}}} \newcommand\R{{\mathrm{I\!R}}} \)

60 B.C. `\quad` (ORF)


The Thrill Goes On: Bernard Yesterday and Today

`\qquad\quad`
Ken Clarkson
IBM Research, Almaden

60BC

Year 60 BC was a year of the pre-Julian Roman calendar. At the time, it was known as the Year of the Consulship of Metellus and Afranius (or, less frequently, year 694 Ab urbe condita). The denomination 60 BC for this year has been used since the early medieval period, when the Anno Domini calendar era became the prevalent method in Europe for naming years.

Events

By place

Roman Republic

Syria

  • The Seleucid Empire comes to an end with the last two Emperors being murdered on orders from Rome.

China


Births

Deaths

?

1955

Filtering search: interval queries

A data structures problem.

Data: set `S` of intervals `[l_1,h_1], [l_2,h_2],\ldots`,
Query: value `q`,
Output: intervals `[l, h]\in S` containing `q`

Filtering search: the data structure

Approach:
Split the real line into apertures so that:
  • Every point in aperture `Z` is in at least half the intervals containing `Z`
  • The total number of interval/aperture pairs that meet is `O(n)`

  • The array of apertures, in sorted order;
  • For each aperture, the intervals `I_Z\subset S` that meet it.
Given `q`:
`\qquad` Find aperture `Z\ni q` via binary search
`\qquad` Report `[l,h]\in I_Z` if `q\in [l,h]`

Query time is `O(A + \log(|S|))` for Answer size `A`

Pretty easy elegant, huh?

  • Output-sensitive queries
    • The idea of
  • Optimal space
  • Why should such a set of apertures exist?
  • This was just the warmup: segment intersection, boxes containing a given point, points contained in a given box, k-NN, circular range search,...
    • The hive graph
    • Fractional cascading

Diffuse Influence Systems

Fish gotta school, birds gotta flock

How to understand these interactions?


Distance parameter `r\gt 0`
`n` agents on the real line
At discrete time step `t`, agent `i` at `x_i` moves to the centroid of the agents within distance `r`

Generalizing: from 1d to 2d

Distance parameter `r\gt 0`
`n` agents in a disk
At discrete time step `t`, agent `i` at `x_i` moves to the centroid of the agents within distance `r`

Generalizing: from 2d to ...

More generally: want to model systems of agents that influence each others' positions:

agent `y_i\in\R^d` influences `y_j\in\R^d`
`\iff`
some first-order predicate on all agents is true

A cleaner (looking) model

Via linearization, tensoring, yada yada, reduces to:

`n` agents `x_i\in\R`, forming point `(x_1,\ldots,x_n)\in X\equiv [-1,1]^n`
At discrete time step `t`, `x_i` moves to "centroid" of agents, specified by:
Arrangement of hyperplanes `\cal A(\cal D)` in `\R^n`
For each `n`-cell `c\in\cal A(\cal D)`, a right stochastic matrix `A^c` (rows sum to one)
At time `t`:
`\qquad x\mapsto f(x) \equiv A^{c(x)} x`, where `x\in c(x)\in \cal A(\cal D)`

A linear map on `c` splits it into pieces, each piece with very different `A`:

Still messy: the Very Slow Clock, 1/2

Suppose
`x_{n-1}= -1, x_n = 1`, and
`x_3,\ldots,x_n` form a "clock" (counter) with period `k`

That is, `x_3\ldots x_n` form `k` states, call them `0,1\ldots k-1`,
and system cycles through them over and over

Suppose `x_1` and `x_2` (using fixed `x_{n-1}` and `x_n`) act as follows:

`[x_1,x_2] \gets \begin{cases} \class{tied_highlightee1}{[-1,1] \text{ initially}}\\ \class{tied_highlightee2}{[(x_1+x_2)/2, x_2] \text{ clock is not zero}}\\ \class{tied_highlightee3}{[-1, x_1] \text{ clock is zero}}\\ \class{tied_highlightee4}{[-1, 1] \text{ when } x_2\lt 0} \end{cases}`

The Very Slow Clock, 2/2


Tied to a clock with `k` states,
`x_2` takes about `2^k` time to become negative

New clock using also `x_1` and `x_2`:

  • States are positions of `x_2`
  • Clock is zero when `x_2\lt 0`
  • Applied recursively, a clock of period about $$2\!\!\uparrow\uparrow\!\!(n/2) = 2^{\left. 2^ { .^{.^{.^{2}}}}\right\} n/2 }$$

Analysis concepts: nesting time, 1/2

Suppose `\tau` is the smallest `t` such that `f^t(X) = f(f(\cdots f(X)` does not meet `\cal D`.
Then `\tau` is the nesting time.

For all `t`, `f^{t+1}(X)\subset f^t(X)`, since `f(X)\subset X`,
so `f^t(X)` does not meet `\cal D` for all `t\ge \tau`

`t` equivalence For `x,y\in X\equiv [-1,1]^d`, say that:
`\qquad x\sim y` if `x,y \in c\in \cal A(\cal D)`
`\qquad x\sim_t y` if `f^i(x)\sim f^i(y)` for `i\in [0,1,\ldots,t]`
If `\tau` is the nesting time,
then `x\sim_{\tau-1} y` implies `x\sim_t y` for all `t\ge \tau`

For `x'=f^{\tau-1}(x)`, `y'=f^{\tau-1}(y)`,
`\overline{x'y'}` does not meet `\cal D`, so `f` on `\overline{x'y'}` is a single linear map
so `\overline{f^t(x')f^t(y')}` doesn't either for `t\ge\tau`

Nesting time, 2/2

That is, if the nesting time is finite:

  • So is the number of blocks (equivalence classes) under `\sim_t`, over all `t`
  • If `U\subset X` is a block, then `f(U)` is contained in another block
    • That is, "nests"
  • The orbits `\{f^t(U)\mid t\ge 0\}` move among the blocks
  • So there is some `t` and `p` such that `f^{t+p}(U) \subset f^t(U)`
    • And so `f^{t+zp}(U) \subset f^t(U)` for `z=0,1,2\ldots`


When should there be a finite nesting time?


Under natural general conditions:
there is a very small `E\subset X`, near `\cal D`, so that
`X\setminus E` has finite nesting time, and
the orbits of `x\in X\setminus E` form limit cycles (vs chaos)

Analyzing `A^{c_t}A^{c_{t-1}}\cdots A^{c_1}`

I've explained everything, except for the hard part

  • The composition `f^t(x)=A^{c_t}A^{c_{t-1}}\cdots A^{c_1}x` for some `c_i`, `i=0\ldots t`
  • Powers of stochastic matrices are well understood, but not these products
  • Analyze sequence, to find either that:
    • Product `A^{c_t}\cdots A^{c_1}` is mixing, or
    • Matrices `A^{c_1},\ldots,A^{c_t}` are block diagonal or block upper triangular
      • Splits of the agents `[n] = S\cup T` where `S` does not depend on `T`
  • Also, assume a kind of weak continuity:
    when `|x_i-x_j|\le\epsilon_0`, condition `A^{c(x)}_{ij}==0` is constant

Conclusions

Happy birthday!