Q The Query Complexity Zoo

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

FileHolds
data/site.yamltitle, navigation, the category list, the three settings, the status vocabulary, the matrix ladder
data/refs.yamlbibliography — a flat map from citation key to entry
data/measures/*.yamlone block per measure, under a top-level measures: list
data/functions/*.yamlwitness families, under functions:
data/relations/*.yamlthe bounds, under relations: — this is the heart of the site
data/tables/*.yamlthe exponent matrix
data/concepts.yamlprose pages
data/open_problems.yamlopen 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 exact upper met by an exact separation 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 exp upper beside an exp separation renders exp, 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 writing unbounded, 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 is exp, 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 is unbounded, and the stmt says 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 a scale: 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. exact composed with exact stays exact, tilde is 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. from is the quantity being bounded. An upper entry on the pair \((M_1,M_2)\) is a statement \(M_1 = O(g(M_2))\); a lower entry 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 total record, with a fails record for partial if there is a counterexample.
  • Bare-LaTeX fields. stmt:, headline: and value: hold LaTeX with no $ delimiters — the templates wrap them. Every other prose field is markdown, where you do write $…$.
  • Confidence. conf: low renders a visible ?. Use it rather than deleting something you are unsure of, and pair it with todo: saying what to check.
  • putative is 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 a note: with the derivation and no badge. Reserve putative: true for a genuine argument worked out for this catalogue, the kind a reader should check before relying on it. The build refuses the badge unless note: 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 to data/functions/ with just id/name/short/refs; the page will show a “definition not yet transcribed” banner until someone fills in formal:.

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.