Q The Query Complexity Zoo

How to read this zoo

Conventions: what O(.) means here, what a 'witness' is, and how confident each entry is.

Relations

Every relation page is about an ordered pair $(\mathrm{M}_1,\mathrm{M}_2)$ in a fixed setting (total / partial / relation), and has two halves:

  • Upper bounds -- statements $\mathrm{M}_1(f)=O(g(\mathrm{M}_2(f)))$ holding for all $f$ in that setting.
  • Lower bounds -- statements $\exists$ a family $f_n$ with $\mathrm{M}_1(f_n)=\Omega(g(\mathrm{M}_2(f_n)))$, together with the witness function family, which links to its own page.

A relation is settled when the two match, gap when they do not, open when the upper bound is conjectural, and fails when no bound exists at all.

The exponent matrix

The big table records one exponent pair per ordered pair of measures: the cell in row $\mathrm{M}_1$, column $\mathrm{M}_2$ records $a,b$ meaning $$\mathrm{M}_1(f) = \Omega\big(\mathrm{M}_2(f)^{a}\big)\ \text{ is witnessed, and }\ \mathrm{M}_1(f) = O\big(\mathrm{M}_2(f)^{b}\big)\ \text{ is a theorem}.$$ A shaded cell means $a<b$ (a gap). Exponents hide $n^{o(1)}$ factors; the per-pair pages carry the fine-grained statements with logs and constants. Each cell cites its sources; a star marks one whose exponent was worked out here, with the argument in the note.

Confidence

Entries carry conf: high | medium | low, reflecting how sure the editor of this zoo is that the statement and attribution are right -- not how sure the community is. Anything marked todo is an admitted gap in this database, not in the literature.