Editing the zoo
All content is YAML under data/. Nothing factual lives in the
templates or in build.py. Edit a file, rebuild, reload.
Build
python3 build.py --strict # fails if any cross-reference is unresolved
python3 build.py --serve 8000 # build then serve at http://localhost:8000/
python3 -m http.server -d site 8000
--strict checks every citation key, every see_also id,
every witness, and every [[wiki-link]] against the union of
measure ids, function ids, concept ids, open-problem ids, relation ids, and reference
keys (including aliases). Use it before committing.
Where things live
| File | Holds |
|---|---|
data/site.yaml | title, navigation, the category list, the three settings, the status vocabulary, the matrix ladder |
data/refs.yaml | bibliography — a flat map from citation key to entry |
data/measures/*.yaml | one block per measure, under a top-level measures: list |
data/functions/*.yaml | witness families, under functions: |
data/relations/*.yaml | the bounds, under relations: — this is the heart of the site |
data/tables/*.yaml | the exponent matrix |
data/concepts.yaml | prose pages |
data/open_problems.yaml | open problems |
Files inside a directory are concatenated in filename order, so
data/relations/08-whatever.yaml is a perfectly good place for new material.
The ladder: list in data/site.yaml is the one piece of
ordering nobody derived: the hand-written rough sort of the measures by size behind the
Ladder scope on the matrix page.
Entries are {id: R, why: 'one terse line'}, biggest first, and
the rule to keep is that if \(X \le Y\) for every total \(f\) then \(Y\) comes first;
everything else is judgement. Ids are checked like any other cross-reference, so a typo
fails the build. Leave out anything with no stable place, and keep one representative per
family of measures that are equal up to constants.
Adding a bound
This is the common case. Append to any file in data/relations/:
relations:
- from: R # the LHS measure id (the matrix ROW)
to: Q # the RHS measure id (the matrix COLUMN)
setting: total # total | partial | relation
status: gap # settled | gap | open | fails
upper:
- stmt: '\mathrm{R}(f) = O\big(\mathrm{Q}(f)^4\big)'
form: {exp: 4, kind: const} # machine-readable shadow of stmt
refs: [ABKRT21]
note: 'Via $\mathrm{R} \le \mathrm{D} = O(\mathrm{Q}^4)$.'
conf: high # high | medium | low
tight: 'up to the exponent'
lower:
- stmt: '\mathrm{R}(f_n) = \tilde\Omega\big(\mathrm{Q}(f_n)^3\big)'
form: {exp: 3, kind: tilde}
witness: pointer # a function id from data/functions/
refs: [ABBLSS17]
conf: high
notes: |
Free markdown. Use $\LaTeX$ freely and [[wiki-links]] to any id.
see_also: [D, adeg, composition]
Both upper and lower are optional. A bound is one bullet;
add as many as you like and they render in order, so put the strongest first.
Give the record an id: if it is about a phenomenon rather than the raw
pair (a composition theorem, an \(\varepsilon\)-dependence); it then gets a stable
anchor and appears on the relations index.
Optional extras: headline, kind: composition,
param: eps, superseded_by: <refkey>.
The form: field, and what the build derives
A stmt is LaTeX for a human. form is the same statement for
the build — the only field the engine reasons with. Without one, a bullet
still renders, it just does not take part in the matrix cells, the tightness chips or the
closure. With one:
form: {exp: 2, log: 1, kind: const} # = O(M2^2 log M2)
exp: the exponent (default 1)
log: how many log factors (default 0)
kind: exact M1 <= M2^exp, no hidden constant
const O(...) or an explicit constant
theta Theta(...): tight both ways -- also gives the converse edge
tilde up to polylogs
exp exponential, on either side (M1 <= 2^M2, or 2^Omega(M2) apart)
log logarithmic, on either side
unbounded no bound at all: M1 is not O(M2^k) for any k
(lower side only -- it is a statement about what fails)
dir: reverse -- this bullet really bounds `to` in terms of `from`,
so file it under the reverse pair rather than claim it here
inherit: false -- do NOT propagate to other settings (side conditions!)
An equivalent: entry on a measure page takes the same field, with
setting: defaulting to total.
What a cell then says
A matrix cell is two exponents, separation, upper, each with a chip naming
how tight it is. The chips on the upper side are the ones above
(= for exact, \(\Theta\), \(\tilde O\), \(O\)); on the
separation side they read the other way (\(\ge\), \(\Theta\), \(\tilde\Omega\),
\(\Omega\)), because a separation is a family attaining the exponent.
- An
exactupper met by anexactseparation at the same exponent with no logs is the strongest state a pair can be in: not just \(M_1 \le M_2\) but a family with \(M_1 = M_2\) on the nose. The build detects this itself — you never mark it — and collapses the cell to a single=, reading “settled — with equality”. Most of the containment chains (\(\mathrm{RS} \le \mathrm{R} \le \mathrm{R}_0 \le \mathrm{D} \le \mathrm{D}^{\mathrm{na}}\)) are settled this way by \(\mathrm{PARITY}_n\). - Non-polynomial pairs still get two entries. An
expupper beside anexpseparation rendersexp, exp: exponentially bounded, and exponentially separated. \(\mathrm{D}^{\mathrm{na}}\) versus \(\mathrm{D}\) is the model case — \(\mathrm{D}^{\mathrm{na}} \le 2^{\mathrm{D}}-1\) always, with equality on \(\mathrm{Nav}_k\). Such a cell is settled; it is not a gap. - Reserve the glyph. \(\infty\) (
unbounded) means a proved impossibility, not an unfilled cell. An unfilled cell is?. Before writingunbounded, check that the ratio really is unbounded — usually because one measure can be held at \(O(1)\) while the other grows, though among the normalized quantities it is the denominator collapsing that does it. If instead the two are exponentially related, that isexp, and the honest cell says so. The build rejects a record that claims no bound exists while another bullet supplies one. There is no separate “no bound of this form” kind: a bound that fails for every exponent isunbounded, and thestmtsays in words what shape of bound was ruled out.
The four derivation rules
- Separations read off the recorded values. A function page lists
\(M(f)\) for as many measures as anyone could find, and any two of those values
are a separation nobody had to write down: \(\mathrm{C}_{\min}(\mathrm{OR}_n)=1\)
against \(\mathrm{UC}(\mathrm{OR}_n)=n\) says that \(\mathrm{UC}\) is not bounded
by any function of \(\mathrm{C}_{\min}\). The build parses the LaTeX of
every value into a growth rate (
growth.py) and compares each ordered pair on each family, producing a polynomial exponent, a \(2^{\Omega(\cdot)}\), or “unbounded”. Three things keep it honest: the numerator must be a lower bound on the first measure and the denominator an upper bound on the second (so an \(O(\cdot)\) value can never witness a separation); a value the parser cannot pin down exactly is skipped, never guessed at; and “unbounded” is claimed only when the denominator settles on a positive constant, since a measure that tends to \(0\) can still be bounded below by a function of itself. Families with two genuinely free parameters are skipped unless ascale:block says which one is the asymptotic parameter. - Transitive closure. \(M_1 \le M_2^{p}\log^{a}M_2\) and
\(M_2 \le M_3^{q}\log^{b}M_3\) give \(M_1 = O(M_3^{pq}\log^{bp+a}M_3)\), up to four
steps.
exactcomposed withexactstays exact,tildeis contagious, and a cycle of exponent below 1 is reported as a data error rather than rendered. - Separations pushed forward. A family with \(M_1 \ge M_2^{p}\), plus a universal \(M_3 = O(M_2^{r})\), separates \(M_1\) from \(M_3\) at exponent \(p/r\) on that same family. The rule also runs on the other index: with a universal \(M_1 = O(M_3^{r})\) the same family separates \(M_3\) from \(M_2\) at exponent \(p/r\), because \(M_3 \ge M_1^{1/r}\) there. So a measure known to be \(\Theta\) of another — \(\mathrm{Corr}\) and \(\mathrm{Sel}\) against \(\mathrm{R}\), say — inherits its whole row of separations, not just its column. “Unbounded” and \(2^{\Omega(\cdot)}\) verdicts are carried along too; a \(\log\) separation is not, since a polynomial lift does not preserve it.
- Setting inheritance. Upper bounds travel from the general to the special
(relation → partial → total); separations travel the
other way (total → partial → relation), since a hard total function is a hard
partial function. Both are gated on the measure being defined in the target setting.
A bound with a side condition — “for search problems with verifiable
outputs” — must carry
inherit: false, or it will quietly become a false theorem about total functions.
Everything derived is labelled as such wherever it appears, is dropped in favour of a recorded statement of the same strength, and is never written back to the YAML. If a derived bound looks wrong, the fix is in the data: read the derivation chain in the tooltip, find the step that overstates, and correct or annotate that record.
Where a pair lives
Pairs have no files. There are 94×94 ordered pairs and the build can say something about a good fraction of them, mostly by derivation, so one page renders all of them:
pair.html?a=D&b=R D versus R
pair.html?a=D&b=R#D__R__total ... at a particular record
pair.html?a=R&b=R the diagonal: composition, parameters
A record's anchor is its id:, which defaults to
<from>__<to>__<setting>. The page reads
api/pair/<row>.json, written by build.py: recorded
relations are pre-rendered HTML (the same Jinja macro this site uses everywhere else),
the derived layer is data. Nothing about a pair is authored in the JSON — edit the
relation record and rebuild.
Conventions worth keeping
- Direction.
fromis the quantity being bounded. Anupperentry on the pair \((M_1,M_2)\) is a statement \(M_1 = O(g(M_2))\); alowerentry is a separation \(M_1 = \Omega(g(M_2))\) on some family. Put the reverse direction in the reverse pair; the two pages link to each other. - Keep the logs. The whole point of the fine-grained layer is that \(O(\mathrm{R}^2\log \mathrm{R})\) and \(\tilde O(\mathrm{R}^2)\) are different statements. Write \(\tilde O\) only when the source does.
- Say which setting. A statement with no setting is a bug. If a bound is
known only for total functions, that is a fact about the bound and belongs
in the
totalrecord, with afailsrecord forpartialif there is a counterexample. - Bare-LaTeX fields.
stmt:,headline:andvalue:hold LaTeX with no$delimiters — the templates wrap them. Every other prose field is markdown, where you do write$…$. - Confidence.
conf: lowrenders a visible ?. Use it rather than deleting something you are unsure of, and pair it withtodo:saying what to check. putativeis for arguments, not for missing citations. A value no paper states but that follows in a line — sandwiched between two recorded values, a recorded \(\Theta\) relation applied once, a Fourier expansion read off — is just a fact: give it anote:with the derivation and no badge. Reserveputative: truefor a genuine argument worked out for this catalogue, the kind a reader should check before relying on it. The build refuses the badge unlessnote:spells the argument out.- Witnesses are ids.
witness: pointer, not “the pointer function”. If the function is not in the catalogue yet, add a stub todata/functions/with justid/name/short/refs; the page will show a “definition not yet transcribed” banner until someone fills informal:.
Cross-references
Anywhere in a markdown field you can write [[D]], [[pointer]],
[[minimax]], [[open-D-vs-bs]], or [[Nisan91]] and
it becomes a link with a sensible label; [[D|the deterministic measure]]
overrides the label. A bare [Nisan91] or [BdW02, Cor. 1] in
prose is auto-linked too, as long as the first token is a known citation key.
Ids are global and must be unique across measures, functions, concepts, open problems, and named relations.
Adding a measure
measures:
- id: Rbar
name: "Expected-cost randomized query complexity"
symbol: '\bar{\mathrm{R}}_\varepsilon(f)'
aliases: ["Las Vegas cost", "expected query complexity"]
category: randomized # must be an id from site.yaml
order: 20 # position within the category
short: "One line, shown in listings."
definition: |
Markdown + $\LaTeX$.
params:
- name: eps
symbol: '\varepsilon'
default: '1/3'
range: '[0, 1/2)'
description: "..."
dependence: |
Markdown block on how the measure moves with the parameter.
settings:
total: {defined: true, note: "..."}
partial: {defined: true, note: "..."}
relation: {defined: false, note: "why not"}
facts:
- '$\bar{\mathrm{R}} \le \mathrm{R}$ always.'
equivalent:
- measure: R
statement: 'Equal up to a constant for total $f$ ...'
form: {exp: 1, kind: theta} # optional; see "form" above
setting: total
refs: [KulkarniTal16]
refs: [BdW02]
see_also: [R, cost-conventions]
confidence: high
Adding it to the matrix is separate and optional: the exponents live in
data/tables/total-exponents.yaml, one cell per pair, and any exponent worked
out here rather than quoted is marked own: true plus an
own_note carrying the argument.
Adding a function, and the scale: block
A function's values: are not decoration: the build compares every pair of
them and turns the comparison into a separation (derivation rule 1 above). That only
works if it knows what the values are functions of.
functions:
- id: MinskyPapert
kind: total # total | partial | relation
arity: '$N = m^3$ bits: $m$ blocks of $m^2$'
scale: {var: m, subs: {N: 'm^3'}} # ← the asymptotic parameter, and
values: # every other name in terms of it
- {measure: D, value: 'N = m^3'}
- {measure: sdeg, value: '\Theta(m) = \Theta(N^{1/3})'}
When every value is written in one variable, scale: can be left out and
the build infers it. Write one as soon as a family uses two names for the same parameter
(\(N\) and \(m\), \(N\) and \(d\)), and prefer the smallest of them as
var: with var: d and subs: {N: '2^d'} a value of
\(N^{0.753}\) stays exact, whereas the other direction would need \(2^{\log_2 N}\).
A family with two genuinely free parameters (\(\mathrm{THR}_k^n\),
\(k\)-distinctness) should have no scale:; the build skips it and says so in
the build report rather than picking one and inventing separations.
Values themselves are plain LaTeX. \(\Theta(\cdot)\) and a bare expression bound the
measure on both sides; \(O(\cdot)\) or \(\le\) only from above; \(\Omega(\cdot)\) or
\(\ge\) only from below — and the build respects that, so an \(O\) value will never
be used as the big side of a separation. Anything with a free \(\varepsilon\), a
\text{if} case split or an unresolved second parameter is skipped.