Recently added

What's new

Essays arrive in groups rather than one at a time. The most recent group is below in full, and every earlier one after it, newest first.

Essays arrive in groups rather than one at a time, and a group usually opens up a subject not covered before. Between one group and the next nothing changes, so a reader who has seen the most recent group has seen everything.

17 September 2026

9 essays on one pass, and no room, the floors, counting, when it does not fit, when the algorithm flips a coin and two parameters

One pass, and no room

A decay measured from where it started

An exponentially decayed counter is one number because its weights fade by elapsed time alone. Forward decay keeps a polynomial weight in one number too, by measuring each arrival from a fixed landmark. Its memory is then a share of the time since that landmark: at β = 2 an arrival counts half at 29% of that time. Anchored at the start of a stream, it takes 5.3 seconds to register a fourfold rise twenty seconds in and 83 seconds when the rise comes at five minutes.

5 figures The floors

Every pair must be asked

Ask whether a six-vertex graph is connected, one pair of vertices at a time, and the best possible algorithm needs all fifteen questions on its worst graph. The claim that this holds for every monotone property of graphs is a conjecture fifty years old. At four vertices it can be settled completely: all 2,046 properties that do not depend on vertex names need every pair. Name one vertex, and the count drops from ten to four.

7 figures The floors

The floor a merge cannot reach

Merging two sorted lists of five keys each has 252 possible outcomes, so counting says eight comparisons might do. Solving the game says nine are needed, and on equal lengths the shortfall keeps growing, as half the logarithm of the length. Averaged over random inputs, though, the same count is missed by a tenth of a comparison. The counting floor is nearly exact on average and wrong in the worst case.

6 figures The floors

The order inside a tie

Sort the rotations of a text by their first four characters rather than by everything that follows, and the output clusters slightly better than the full Burrows–Wheeler transform: 1.780 bits a symbol against 1.802, from 63% of the character reads. It also costs nothing to undo. The prediction that a shorter context leaves ties for the inverse to pay for was wrong. The cost to undo comes from how a tie is ordered, not from how long the context is, and at k = 0 the wrong tie rule is exactly the sort.

6 figures Counting

The price of remembering an answer

Give selection sort a table of the pairs it has already compared and it makes 16,805 comparisons on 256 elements instead of 32,640. The table pays for itself once a comparison costs more than 3.1 word operations, and that price stays near three at every size measured. Give it the full closure of everything its answers imply and it makes 13,079. The closure pays only past 425 operations a comparison at that size, and past 1,659 at twice the size. The cheap memory is worth having on long keys. The complete one is worth having almost nowhere.

5 figures When it does not fit

A key passed along the row

A full B+-tree leaf that offers a key to its immediate neighbours before splitting leaves an ascending stream 67.2% full. Let it look one sibling further and the same stream fills its leaves completely, 2,048 leaves where there were 3,048, for about the same key moves. On random keys each doubling of the reach adds a few points of fill and more writes than it saves, and at the whole parent a key travels sixteen leaves on average. On a stream that is mostly in order the same reach costs almost nothing.

5 figures Counting

The comparisons that name the answer

Returning the 4,000 smallest of 65,536 keys in order needs 61,536 comparisons to eliminate the rest and 42,100 to order the ones returned. That was the floor, 103,636, and a tournament made 125,388. What the floor never charged is saying which 4,000 come back. Charge that, and the floor is 125,341. On the same input the tournament is 47 comparisons above it, and for every k up to a hundred it is exactly on it.

5 figures When the algorithm flips a coin

Two blocks and the chances they add

Send each key to the emptier of two 512-bit blocks and the busiest block of a filter at sixteen bits a key holds 38 keys instead of 55. The false-positive rate does not move: 0.100% against 0.095%. At eight bits a key it doubles. A lookup cannot tell which block a key went to, so it has to ask both, and asking twice is two chances to be wrong. The repair that tames a hash table's worst bucket buys a filter nothing that a block twice as wide does not.

5 figures Two parameters

A potential mended where it broke

A stored reweighting on a 256-vertex graph with negative arcs costs 10,045 relaxations to rebuild, and rebuilding it every time an update breaks it stops paying once half a per cent of arcs change between queries. Mending it from the arcs that broke costs 16 to 442 relaxations instead, and the stored potential stays at two thirds of the per-query cost at every rate of change. When the change is a vertex whose costs all move together, a repair reaches nearly every vertex. It still costs a third of a rebuild.

6 figures

Before that

Everything published earlier, newest first. Titles only — the cards are on the full listing.

16 September 2026

6 essays on one pass, and no room, the floors, when the algorithm is a table and counting

The error of a difference — one pass, and no room
What a reordering costs to undo — the floors
The columns the candidates share — when the algorithm is a table
The lattice that decides the ties — when the algorithm is a table
Two floors that can be added — counting
The questions a sort asks twice — counting

15 September 2026

14 essays on when the algorithm is a table, counting, when it does not fit, when the algorithm flips a coin, two parameters and what the machine does

The bound a block can and cannot have — when the algorithm is a table
The order equal keys keep — counting
The sort that makes none of them — counting
What a planner pays to find out what to pay — when it does not fit
The sibling a full leaf asks first — when it does not fit
A summary's silence is a bound, not a count — when it does not fit
The bits given to the wrong keys — when the algorithm flips a coin
The read a filter has no key for — when it does not fit
What the queries know that the map does not — two parameters
A stop that is correct and never sooner — two parameters
Positions confined to one line — when the algorithm flips a coin
A lookup that stops caring how wide an entry is — what the machine does
How long a reweighting stays true — two parameters
Eight cells at once — what the machine does

12 September 2026

19 essays on when the algorithm is a table, counting, when it does not fit, when the algorithm flips a coin, two parameters and what the machine does

The split scan cut into blocks — when the algorithm is a table
The bound the search finds for itself — when the algorithm is a table
The worst case found by climbing — counting
A worst case ten positions wide — counting
The skew a few counters cannot repair — when it does not fit
The ties a rounded matrix makes — when the algorithm is a table
The sort whose count has no distribution — counting
What insurance against an estimate costs — when it does not fit
A filter that grows by moving a bit — when the algorithm flips a coin
Runs twice as long as memory — when it does not fit
The count of the part that was read — counting
A bound right for the wrong reason — two parameters
The keys that arrive late — when it does not fit
Two hash values and the keys they copy — when the algorithm flips a coin
Two estimates that must agree — two parameters
One Bellman–Ford buys every Dijkstra — two parameters
Where the landmarks stand — two parameters
The bucket that fits a line — what the machine does
The table stored the way it is filled — what the machine does

11 September 2026

20 essays on two parameters, when the algorithm is a table, counting, when it does not fit, when the algorithm flips a coin and what the machine does

A graph is as hard as its largest cycle — two parameters
The matrix a corpus wrote — when the algorithm is a table
An estimate borrowed from an easier problem — two parameters
The parameter plane has few answers — when the algorithm is a table
A distribution computed rather than sampled — counting
A triangle stored in a square — when the algorithm is a table
An estimate is a reweighting — two parameters
The estimate a plan rests on — when it does not fit
The intersection two filters cannot report — when the algorithm flips a coin
A count over every input — counting
More hashes or wider buckets — when the algorithm flips a coin
The permutation that moves almost nothing — when it does not fit
Where two searches should stop — two parameters
The join order is a guess — when it does not fit
The tie that breaks left — when the algorithm flips a coin
A filter past its design size — when the algorithm flips a coin
The filter each run carries — when it does not fit
Choices that are not independent — when the algorithm flips a coin
The order with the best depth — what the machine does
Two probes are two misses — what the machine does

10 September 2026

20 essays on when the algorithm is a table, two parameters, when the algorithm flips a coin, when it does not fit and counting

The cells are not the cost — when the algorithm is a table
The precondition on a function the caller writes — two parameters
The precondition that removes the queue — two parameters
The zero that moves the answer out of the corner — when the algorithm is a table
Two passes or one, and what the second one costs — two parameters
A distance divided by a length is not a rate — when the algorithm is a table
An insertion that can fail — when the algorithm flips a coin
The argmin that cannot go backwards — when the algorithm is a table
The edit that reaches back two rows — when the algorithm is a table
The order that has a depth — when the algorithm is a table
The second choice — when the algorithm flips a coin
Two parameters are not enough either — two parameters
One dial between two structures — when it does not fit
The cells that were never worth having — when the algorithm is a table
The evidence a filter cannot remove — when the algorithm flips a coin
Permuting is the harder problem here — when it does not fit
The exchange rate nobody wrote down — counting
The count that came from somewhere else — counting
The index that is not worth reading — when it does not fit
Two ways to join, and the ratio that decides — when it does not fit

5 September 2026

50 essays on the floors, the data that is not a number, what the machine does, what a bound is, the index that replaces the text, what is taught wrongly, structures, the other axis and what the libraries do

Work that falls as the answer grows — the floors
Proportional to the answer, not the alphabet — the floors
From the right, two of sixteen — the floors
The cell nobody filled — the data that is not a number
What repetition is worth once the logarithm is gone — the data that is not a number
The array is the length distribution — the data that is not a number
A node costs two ranks — what the machine does
Twenty bits apart — what the machine does
A code word is at least one bit — what a bound is
Two at binary, five at twenty-six — what a bound is
What a character costs on four machines — what the machine does
The index that does not notice — the index that replaces the text
The flat bottom of a shallow curve — what a bound is
Flat in the budget, and not — what a bound is
A boundary that costs nothing — what is taught wrongly
The price of a boundary is what precedes it — structures
The tree answers the question — the index that replaces the text
The exponential is in the expression — what a bound is
One copy per document is one occurrence per document — what is taught wrongly
The last array in the apparatus — structures
Two currencies for one separator — the other axis
Asking about symbols that are not there — the index that replaces the text
The array that says where is twice the samples — the other axis
A collection is a construction — what the libraries do
A saving quoted without its collection — what is taught wrongly
The apparatus, three times smaller again — the other axis
The branches that find nothing — structures
The smaller tree hands it back unsorted — what the libraries do
What the locating apparatus becomes — the index that replaces the text
Three savings on one structure — the index that replaces the text
A looser budget wastes a larger share — what the libraries do
A walk that does not prune — what is taught wrongly
One set, three orders — what is taught wrongly
A position split in two — structures
The ladder, and the rung that spends — the other axis
Every copy points right — structures
The same occurrences, less bookkeeping — the index that replaces the text
A price with no structure under it — what is taught wrongly
Where the sparse representation loses — what is taught wrongly
The floor was the marks — what the libraries do
Bits and steps on one frame — structures
The saving that is a loss — what the libraries do
Two factors that do not multiply — what is taught wrongly
Half an index is three permutations — the other axis
Two states per operator — structures
A constant factor, not a term — what is taught wrongly
The scan the order does not touch — what the libraries do
A cache below the reachable set — what is taught wrongly
Where the table starts paying — what the libraries do
The folklore is about a matcher — what is taught wrongly

1 September 2026

20 essays on the data that is not a number, what is taught wrongly, the index that replaces the text, what the libraries do, structures, the other axis, what the machine does and what a bound is

A million characters of the same thing — the data that is not a number
The half of a fall that is the logarithm — what is taught wrongly
Two thousand documents of two hundred characters — the index that replaces the text
The crossing that never arrives — what the libraries do
The shape of a real history's depth — the data that is not a number
One revision, one level — structures
The deepest text is punctuation — what is taught wrongly
The cap that would ship — what the libraries do
The half that is never asked where — the index that replaces the text
An index that cannot locate — the other axis
A sixth of what, exactly — what is taught wrongly
The saving, spent — what the libraries do
Every child at once — the index that replaces the text
The count that was already there — what the machine does
The tree the operation insists on — structures
A factor of fourteen, for four per cent — what a bound is
The array the walk never reads — the index that replaces the text
A document already in the answer — structures
What the chain cost — the other axis
The apparatus that is smaller than its index — what the libraries do

31 August 2026

20 essays on what the machine does, what the libraries do, what a bound is, the index that replaces the text, the data that is not a number, the other axis, structures and what is taught wrongly

The table that fits inside a block — what the machine does
The number that would choose a cap — what the libraries do
What the generated collection was right about — what the libraries do
Where a crossing moved to — what a bound is
An interval that grows at both ends — the index that replaces the text
The cap an automaton cannot see — what a bound is
The search that starts in the middle — the data that is not a number
A block, a class and an offset — the index that replaces the text
The parse in one pass of the text — the data that is not a number
A corpus that was not generated — the data that is not a number
Documents that are not the same length — the index that replaces the text
Two bits a value, and what undoes them — the other axis
The structure that was supposed to halve — the other axis
A bit for every bit — the other axis
The shape a range question is about — structures
The runs a permutation does not leave — structures
A schedule nobody writes down — what is taught wrongly
The level where compression stops paying — what is taught wrongly
What a quadratic construction was setting — what is taught wrongly
The dial that has no setting — what is taught wrongly

30 August 2026

20 essays on what a bound is, what the libraries do, the data that is not a number, the index that replaces the text, the other axis, structures and what is taught wrongly

The branch that cannot reach an answer — what a bound is
Where the exact rules pay now — what the libraries do
A parse that will not follow a long chain — the data that is not a number
The candidates a filter cannot avoid — the index that replaces the text
The case a failure link does not cover — what a bound is
The cost that is the size of the answer — what a bound is
The errors the rest of the pattern needs — the data that is not a number
What a ceiling costs in phrases — the index that replaces the text
A list of documents is not a list of occurrences — the index that replaces the text
The structure paid for before the first query — the other axis
The table the links already knew — the data that is not a number
The term that came back — the other axis
A bound that has to be paid for — the other axis
One separator, or one for each — the other axis
A rectangle over a permutation — structures
The operations a candidate count leaves out — what is taught wrongly
The cap that binds on one text and not another — what is taught wrongly
The pruning that loses an occurrence — what is taught wrongly
The ratio that was an implementation — what is taught wrongly
The occurrences a join invents — what is taught wrongly

28 August 2026

20 essays on the index that replaces the text, what the machine does, the data that is not a number, what a bound is, what the libraries do, the other axis and what is taught wrongly

The sampling that follows the runs — the index that replaces the text
A function with r pieces — what the machine does
The occurrence carried through the search — the index that replaces the text
The phrases a text copies from itself — the data that is not a number
An index with z in its size — the index that replaces the text
The branches an error opens — what a bound is
The occurrences that cross a boundary — the data that is not a number
The q-grams an error cannot destroy — the data that is not a number
The rule that pays on a long enough text — what the libraries do
The search that spends a budget — the index that replaces the text
The table that walks every pair — what a bound is
The collection decides which index is small — the index that replaces the text
The shift somebody published — the data that is not a number
Every occurrence at the same price — the other axis
The character that costs a chain — the other axis
A sampling that costs more than the array — what is taught wrongly
The measure that cannot see the alphabet — what is taught wrongly
The threshold that reaches zero — what is taught wrongly
Three savings in three currencies — what is taught wrongly
What the approximation gives up — what is taught wrongly

27 August 2026

10 essays on the floors, the other axis, one pass, and no room, structures and what is taught wrongly

The floor charged at every level — the floors
The tuples a summary does not report — the other axis
A floor with two variables in it — the floors
The period that is not a promise — one pass, and no room
The fold that minimises the wrong thing — structures
The sampler that cannot alias — what is taught wrongly
The shape one structure will not fold — structures
A parameter that waits for another — what is taught wrongly
The floor a merge does not settle at — what is taught wrongly
The warning that is silent for the right reason — what is taught wrongly

26 August 2026

10 essays on what a bound is, what the libraries do, the other axis, one pass, and no room, structures and what is taught wrongly

What a fold charges per level — what a bound is
Sized for a rate that does not hold still — what the libraries do
The cheap tail and the expensive merge — the other axis
The floor a histogram already knows — one pass, and no room
The tuples a merge does not give back — one pass, and no room
The window that is even in the wrong currency — one pass, and no room
The bill a partition only divides — structures
The histogram that cannot see the order — what is taught wrongly
The shape that moves the bill — structures
The boundary that hides the burst — what is taught wrongly

24 August 2026

10 essays on one pass, and no room, structures, what is taught wrongly, the other axis, what the libraries do and the floors

The state a merge is standing in for — one pass, and no room
The partition the analysis did not mention — one pass, and no room
The order nobody fixed — structures
The promise that does not survive the tree — what is taught wrongly
A window that is a duration — one pass, and no room
The window that is not full — what is taught wrongly
The clock that cannot see the burst — the other axis
The counter with no window in it — one pass, and no room
The fading nobody computes — what the libraries do
The pass that runs the other way — the floors

23 August 2026

10 essays on the data that is not a number, the floors, the index that replaces the text, what the machine does, the other axis and what is taught wrongly

The shift a set of patterns allows — the data that is not a number
A floor under a run count — the floors
The filter that feeds the table — the data that is not a number
The sampling that goes the other way — the index that replaces the text
The entropy that cannot see a copy — the data that is not a number
The index that stores the runs — the index that replaces the text
Select is not rank backwards — what the machine does
What is still proportional to n — the other axis
The ceiling the shortest pattern sets — what is taught wrongly
The filter that proposes everything — what is taught wrongly

21 August 2026

10 essays on what a bound is, one pass, and no room, the other axis, the floors, structures and what is taught wrongly

The pass that was never a parameter — what a bound is
The bits that say when — one pass, and no room
What a second pass buys — the other axis
A register that became a list — one pass, and no room
A floor one pass cannot get under — the floors
An error measured against the answer — one pass, and no room
The count that outlives its arrivals — structures
The counter that takes the smallest slot — structures
Two structures that are one — what is taught wrongly
The digest that promises nothing — what is taught wrongly

20 August 2026

10 essays on the index that replaces the text, when the algorithm is a table, what the machine does, the data that is not a number, the other axis, the floors and what is taught wrongly

An index larger than what it indexes — the index that replaces the text
A search that runs backwards — the index that replaces the text
The index that is smaller than the text — the index that replaces the text
A cost that is not one — when the algorithm is a table
A cell that has to know where it is — when the algorithm is a table
Rank is the only thing it does — what the machine does
The row that starts at zero — the data that is not a number
The text that does not have to be kept — the other axis
A floor that holds if something else does — the floors
A distance that is not a distance — what is taught wrongly

19 August 2026

10 essays on one pass, and no room, what a bound is, the other axis, when the algorithm flips a coin, the floors, what is taught wrongly and structures

The estimate that squares the stream — one pass, and no room
The error that is on the rank — one pass, and no room
The model a bound was quoted in — what a bound is
What a window costs in bits — the other axis
The independence an estimator spends — when the algorithm flips a coin
The summary that has to forget — one pass, and no room
The floor under a window — the floors
When the stream takes it back — what is taught wrongly
A promise about the rank is not a promise about the value — what is taught wrongly
A sketch that is allowed to be under — structures

18 August 2026

10 essays on when the algorithm is a table, the other axis, the data that is not a number, what the machine does, what is taught wrongly and structures

The cost is the number of subproblems — when the algorithm is a table
The same table, filled two ways — when the algorithm is a table
A band as wide as the answer — when the algorithm is a table
The table nobody has to keep — the other axis
A distance that is a path through a grid — the data that is not a number
The alignment that fits in one line — the other axis
A column computed in machine words — what the machine does
One pass for every pattern at once — the data that is not a number
A table wider than its input — what is taught wrongly
Every substring, in fewer states than substrings — structures

16 August 2026

10 essays on one pass, and no room, when the algorithm flips a coin, the floors, what is taught wrongly and structures

The answer that is allowed to be wrong — one pass, and no room
Counting past what the register holds — one pass, and no room
A count that is never under — one pass, and no room
A count read off the leading zeros — one pass, and no room
The correction that makes it work — one pass, and no room
The estimate that is a median of means — when the algorithm flips a coin
The floor under a summary — the floors
The guarantee that is one query wide — what is taught wrongly
The items that survive k counters — structures
The summaries that add — structures

15 August 2026

10 essays on the data that is not a number, when the algorithm flips a coin, what the libraries do, the floors, what is taught wrongly and structures

The comparison that is not one comparison — the data that is not a number
The shift the pattern already knows — the data that is not a number
The text that answers without reading it — the data that is not a number
The model is the compressor — the data that is not a number
The transform that emits nothing — the data that is not a number
A match decided by a number — when the algorithm flips a coin
The dictionary that builds itself — what the libraries do
The bits a coder emits — the floors
The optimal code that is beaten — what is taught wrongly
The index that is the text — structures

14 August 2026

8 essays on when it does not fit, what is taught wrongly, the floors, what the machine does and structures

One access, eight kilobytes — when it does not fit
Sorting what will not fit — when it does not fit
The layout that is told nothing — when it does not fit
The writes nobody counted — when it does not fit
The block that is not a block — what is taught wrongly
The floor under moving data — the floors
Two searches, one comparison count — what the machine does
A tree with nodes the size of a block — structures

11 August 2026

12 essays on what the libraries do, what the machine does, what a bound is, structures, counting and what is taught wrongly

The sort the library ships — what the libraries do
A run is a property of the input — what the libraries do
When galloping pays — what the libraries do
The pattern that defeats the pattern — what the libraries do
The branch the machine guesses — what the machine does
The threshold somebody chose — what the libraries do
A search with no branch to miss — what the machine does
The depth limit that almost never fires — what a bound is
The probe nobody waits for — structures
Two pivots and what they cost — counting
A bucket that becomes a tree — structures
The invariant that was wrong for seven years — what is taught wrongly

10 August 2026

12 essays on when the algorithm flips a coin, what a bound is, counting, what is taught wrongly, structures and the floors

A structure made of coin flips — when the algorithm flips a coin
The height is a distribution, and the coin is a parameter — when the algorithm flips a coin
One pass, k slots, and two randomness budgets — when the algorithm flips a coin
A filter that is allowed to be wrong — when the algorithm flips a coin
Expected is not average — what a bound is
A hash is a family, not a function — when the algorithm flips a coin
Counting the coin flips — counting
The formula everybody sizes filters with — what is taught wrongly
The priority nobody supplied — structures
What derandomising costs — what a bound is
A floor on the bits — the floors
The adversary who knows the seed — what is taught wrongly

5–8 August 2026

34 essays on counting, two parameters, the other axis, what is taught wrongly, what the machine does, the floors, structures and what a bound is

Counting instead of timing — counting
Counting on a graph — two parameters
Measuring what an algorithm keeps — the other axis
The words "on average" are not a number — what is taught wrongly
The count is not the time — what the machine does
The floor under every comparison sort — the floors
What amortised means — structures
What O-notation does not say — what a bound is
Choosing a growth factor — structures
Fitting a class to measurements — counting
How close anything gets to the floor — the floors
The cliff where the data stops fitting — what the machine does
The constant the notation drops — what a bound is
The stack nobody counts — the other axis
Two parameters, one bound, no order — two parameters
What randomising the pivot buys — what is taught wrongly
A limit is not a prediction — what a bound is
One run, four counts, four answers — counting
The floor moves when the question does — the floors
The frontier between time and space — the other axis
The probe formula nobody checks — what is taught wrongly
The tree that is a list — structures
Where an algorithm looks — what the machine does
The queue decides the class, and the pseudocode does not name it — two parameters
Building a heap from the bottom — structures
In place is a claim, and it is usually wrong about quicksort — what is taught wrongly
The adversary who hides the edge — the floors
The constant that is practically constant — two parameters
The count somebody chose — counting
The space the model does not see — the other axis
Where insertion sort actually wins — what the machine does
A list and a block of memory — two parameters
The floor when the values repeat — the floors
The bound with a precondition — two parameters

Every essay, by subject · by subject · by thread · search