Q The Query Complexity Zoo

The Query Complexity Zoo

Measures, relations, and separations for Boolean decision trees

A browsable, editable catalogue of query-complexity measures and everything known about how they relate -- upper bounds with log factors, matching separations with witnesses, and the partial / total / relational distinctions.

What this is

Query complexity has a lot of measures and a lot of folklore. This site tries to put the folklore in one place, in a form you can grep, correct, and extend.

For each ordered pair of measures \((M_1, M_2)\) we record, separately for each of the three settings:

  • the best known upper bound — a statement \(M_1(f) = O(g(M_2(f)))\) that holds for every \(f\) in the setting, with log factors kept rather than swept into \(\tilde O\) where anyone has bothered to pin them down;
  • the best known lower bound / separation — a family \(\{f_n\}\) with \(M_1(f_n) = \Omega(g(M_2(f_n)))\), together with a link to the function that witnesses it;
  • whether the two meet (Settled), leave a Gap, are Wide open, or whether the relation provably has no bound in that setting.

Start with the exponent matrix for the classical 13-measure picture, then click into a cell for the fine-grained statements. Any of the 94×94 ordered pairs — including the ones where the only thing to say is what the build can derive — opens in the pair browser. How to read the tables explains the conventions.

The three settings

Almost every interesting subtlety in this subject is a setting distinction, so it is a first-class axis everywhere on this site.

total Total functions

f : {0,1}^n -> {0,1} defined on the whole cube. Where all measures are polynomially related.

partial Partial functions

f : Dom(f) -> {0,1} with Dom(f) a proper subset of the cube (promise problems). Most polynomial relations FAIL here.

relation Relations

f subset of {0,1}^n x O : any output o with (x,o) in f is acceptable. Search problems, TFNP-style.

More: Total vs partial vs relational.

The measures