Ken Clarkson

IBM Research, Almaden

IBM Research, Almaden

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.

- Gaius Julius Caesar suppresses an uprising and conquers all of Lusitania for Rome
- Creation of the First Triumvirate, an informal political alliance between Julius Caesar, Pompey the Great and Marcus Licinius Crassus (or 59 BC)

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

- The Han Dynasty government establishes the Protectorate of the Western Regions, the highest military position of a military commander on the Western frontier (Tarim Basin).

- Prince Ptolemy of Egypt, later Pharaoh Ptolemy XIV of Egypt (or 59 BC) (d. 44 BC)

- Aretas III Philhellene, king of Petra
- Su Wu (b. 140 BC)

- January 7 – Marian Anderson is first African-American singer to perform at the Metropolitan Opera in New York City.
- January 22 – The Pentagon announces a plan to develop intercontinental ballistic missiles (ICBMs) armed with nuclear weapons.
- March – A young Jim Henson builds the first version of Kermit the Frog.
- March
2
- Claudette Colvin, a fifteen-year-old African-American
girl, refuses to give up her seat on a bus in Montgomery,
Alabama, to a white woman after the driver demands it. She
becomes a plaintiff in
*Browder v. Gayle*(1956) which rules bus segregation to be unconstitutional. - March 5 - Elvis Presley makes his television debut on "Louisiana Hayride" carried by KSLA-TV Shreveport.
- March
20 – The movie adaptation of Evan Hunter's novel
*Blackboard Jungle*premieres in the United States, featuring the famous single "Rock Around the Clock" by Bill Haley & His Comets. - April 12 – The Salk polio vaccine receives full approval by the Food and Drug Administration.
- April 15 - Ray Kroc opens his first McDonald's in Des Plaines, Illinois.
- April 18 – The first DON'T WALK Pedestrian crossing signals are installed in New York City.
- June 26 – Freedom Charter of the anti-apartheid South African Congress Alliance adopted.
- July 17 – Disneyland opens to the public in Anaheim, California.
- July 18 - The first nuclear-generated electrical power is sold commercially, partially powering the town of Arco, Idaho.
- August
26 – Release in India of Satyajit
Ray's film
*Pather Panchali*. - August
27 – First edition of the
*Guinness Book of Records*is published, in London. - September
2 – Under the guidance of Dr. Humphry
Osmond, Christopher
Mayhew ingests 400 mg of mescaline
hydrochloride and allows himself to be filmed as part of a
*Panorama*special for BBC TV in the U.K. that is never broadcast. - September
10 – The long-running program
*Gunsmoke*debuts on the CBS-TV network. - October
20 –A concert at Brooklyn
High School (Ohio), features Pat
Boone and Bill
Haley & His Comets and opening with Elvis
Presley, Elvis's first filmed performance, for a documentary on
Randle titled
*The Pied Piper of Cleveland*. - November 1 - The Vietnam War begins between the South Vietnam Army and the North Vietnam Army.
- November 5 – Racial segregation is outlawed on trains and buses in interstate commerce in the United States.
- November
20 – Bo
Diddley makes his television debut on Ed
Sullivan's
*Toast Of The Town*show. - December 1 – In Montgomery, Alabama, Rosa Parks refuses to obey bus driver James F. Blake's order that she give up her seat to make room for a white passenger and is arrested, leading to the Montgomery Bus Boycott.
- December 14 - The Tappan Zee Bridge over the Hudson River in New York State opens to traffic.
- December 22 – American cytogeneticist Joe Hin Tjio discovers the correct number of human chromosomes, forty-six.

**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`

Split the real line into

- 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]`

`\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`

- 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

- The

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`

`n`

At discrete time step `t`, agent `i` at `x_i` moves to the centroid of the agents within distance `r`

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`

`n`

At discrete time step `t`, agent `i` at `x_i` moves to the centroid of the agents within distance `r`

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

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)`

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`:

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}`

Tied to a clock with `k` states,

`x_2` takes about `2^k` time to become negative

`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 }$$

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*.

Then `\tau` is the

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]`

`\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`

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`

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)

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)

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

Happy birthday!