Peter van Emde Boas

Peter van Emde Boas was born in Amsterdam on 3 April 1945 and took his doctorate at the University of Amsterdam in 1974 under Adriaan van Wijngaarden, who had built the Netherlands' first computers at the Mathematical Centre. He spent his career as a professor at Amsterdam, in mathematics, computer science and the Institute for Logic, Language and Computation, working on algorithms, complexity and the models of machines that computer science reasons about.

A computer often keeps a set of numbers and asks: what is the next one after x? Schedulers, routers and simulations ask it millions of times a second. A sorted list or balanced tree answers by comparing, one decision at a time, and needs about as many steps as the numbers have bits: up to 64 for 64-bit numbers.

Van Emde Boas's 1975 idea was to stop comparing whole numbers and split each one into its high half and its low half:

$x=\text{high}(x)\cdot \sqrt{M}+\text{low}(x)$

• M: how many possible numbers there are, 2 to the power of the bit count
• √M: the size of each cluster, and also how many clusters there are
• high(x): the top half of x's bits: which cluster it lives in
• low(x): the bottom half: where inside that cluster

Every cluster is itself a smaller van Emde Boas tree, and so is a summary that records which clusters hold anything. The trick that makes it fast: each cluster remembers its own smallest and largest number. So to find the next number after x, the tree asks one question, “is there anything after x in its own cluster?”, and then recurses into only one place: the cluster, or the summary. Never both.

Each call throws away half of the bits, and does a fixed amount of work before it does:

$T(m)=T\left(\frac{m}{2}\right)+c\Rightarrow T={\log }_{2}m={\log }_2{\log }_{2}M$

• m: the number of bits in a key
• T(m): steps to answer one query about m-bit keys
• c: the small fixed work per call: split x, check one min or max
• log₂ m: how many times you can halve m before reaching one bit

For 64-bit numbers that is 6 steps instead of up to 64. The cost is memory: the plain tree reserves room for every possible number, so later versions with hashing keep only what is stored. The van Emde Boas tree is still the standard textbook example of beating the comparison bound by using the bits of the keys themselves.

A lattice is a grid of points made by adding whole-number copies of a few arrows. The same lattice can be built from short, square arrows or from long, skewed ones that make it look like noise. The shortest vector problem asks: given the skewed arrows, find the shortest non-zero point.

${\lambda }_1={\min }_{(i,j)\ne (0,0)}\Vert i{\mathbf{b}}_1+j{\mathbf{b}}_2\Vert$

• b₁, b₂: the two arrows you are given
• i, j: any whole numbers, not both zero
• ‖ ‖: length
• λ₁: the length of the shortest point in the lattice

In a 1981 Amsterdam report van Emde Boas proved that finding the closest lattice point to a target is NP-hard, and that finding the shortest vector is too when length is measured by the largest coordinate. He conjectured it for ordinary length; Miklós Ajtai proved that in 1998, for randomized reductions. In two dimensions a few swaps solve it. In hundreds of dimensions no one, classical or quantum, knows a fast way, which is why NIST's 2024 post-quantum standard ML-KEM is built on lattices.