Q The Query Complexity Zoo

Measures

Every complexity measure the zoo knows about, grouped by flavour. The // columns say whether the measure is defined for total / partial / relation problems.

Deterministic

Decision-tree depth, size, and distributional variants.

SymbolName totalpartialrelation Parameters What it is
\(\mathrm{D}(f)\) Deterministic query complexity
D
Minimum worst-case number of queries of a deterministic decision tree computing f.
\(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity
Dna
Fewest queries when the whole query set must be fixed in advance.
\(\mathrm{DTsize}(f)\) Decision tree size
D_size
Minimum number of leaves of a deterministic decision tree computing f.
\(\mathrm{rank}(f)\) Decision tree rank
rank
The "Strahler number" of a decision tree: how much branching, rather than how much depth, the tree needs.
\(\mathrm{D}^{\oplus}(f)\) Parity decision tree complexity
PDT
Decision tree depth when each query may read the parity of an arbitrary subset of bits.
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity
D_prod
\(\varepsilon\) Max over product input distributions of the bounded-error distributional query complexity.
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity
Dmu
\(\varepsilon\)\(\mu\) Least depth of a deterministic tree that is correct except with probability eps under the input distribution mu.

Randomized

Bounded error, zero error, expected cost, noisy oracles.

SymbolName totalpartialrelation Parameters What it is
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity
R
\(\varepsilon\) Worst-case number of queries of a randomized decision tree that errs with probability at most eps.
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity
Rbar
\(\varepsilon\) Same as R_eps but the cost is the expected (not worst-case) number of queries.
\(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity
Rna
\(\varepsilon\) Bounded-error cost when the query set is drawn from a distribution fixed in advance, independent of the answers.
\(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity
R0
Expected number of queries of a randomized algorithm that is always correct.
\(\mathrm{R}^{1}(f)\) One-sided-error randomized query complexity
R1
\(\varepsilon\) Randomized complexity when errors are allowed on only one side.
\(\mathrm{R}_{\mathrm{RP}}(f)\) One-sided randomized queries with certain rejection
R1RP
Negative inputs always reject; positive inputs accept with probability at least 2/3.
\(\mathrm{psD}(S)\) Pseudo-deterministic query complexity
psD
Randomized cost of a search algorithm that must output the same canonical answer with high probability on every input.
\(\mathrm{N}_{p}(f)\) Noisy decision tree complexity
Np
\(p\) Number of queries when every query answer is independently flipped with probability p.

Quantum

Bounded error, exact, post-selected, robust.

SymbolName totalpartialrelation Parameters What it is
\(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity
Q
\(\varepsilon\) Number of applications of the phase/bit oracle O_x needed to compute f with error <= eps.
\(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity
QE
Number of queries of a quantum algorithm that outputs f(x) with probability 1.
\(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity
Q0
Quantum algorithm that never errs but may output "don't know" with probability <= 1/2.
\(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity
PostQ
\(\varepsilon\) Quantum queries when the algorithm may post-select on an exponentially unlikely event.
\(\mathrm{QC}(f)\) Quantum certificate complexity
QC
Quantum analogue of certificate complexity; the square root of RC.
\(\mathrm{NQ}(f)\) Nondeterministic quantum query complexity
NQ
Quantum algorithm with nonzero acceptance probability exactly on 1-inputs.
\(\mathrm{QS}_{\mathrm{weak}}(f)\) Weak quantum sabotage complexity
QSweak
Quantum queries to distinguish stars from daggers in a sabotaged input, without access to its completions.
\(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity
robustQ
\(p\) Quantum queries when the oracle is noisy (each query answer is corrupted).
\(\mathrm{QS}_{\mathrm{str}}(f)\) Strong quantum sabotage complexity
QSstr
Quantum sabotage decision with query access to both opposite-output completions.
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{weak}}(f)\) Weak quantum sabotage index complexity
QSweakind
Find a sabotaged coordinate with quantum access to the sabotaged string alone.
\(\mathrm{QS}^{\mathrm{ind}}_{\mathrm{str}}(f)\) Strong quantum sabotage index complexity
QSstrind
Find a sabotaged coordinate with quantum access to both completions and the sabotaged string.
\(\mathrm{Q}_{\mathrm{E}}^{\mathrm{cert}}(f)\) Exact quantum certification complexity
QEcert
Worst-case exact quantum query cost of recognizing a known input against all opposite-output inputs.
\(\mathrm{Q}_{0}^{\mathrm{cert}}(f)\) Zero-error quantum certification complexity
Q0cert
Zero-error quantum cost of the certification task; equivalent to its exact quantum cost.

Polynomial degree

Exact, approximate, sign, rational, nondeterministic, mod-p.

SymbolName totalpartialrelation Parameters What it is
\(\deg(f)\) Exact degree
deg
Degree of the unique multilinear real polynomial that represents f exactly.
\(\widetilde{\deg}_{\varepsilon}(f)\) Approximate degree
adeg
\(\varepsilon\) Least degree of a polynomial that approximates f pointwise to within eps.
\(\widetilde{\deg}_{+}(f)\) One-sided approximate degree
odeg
\(\varepsilon\) Approximate degree when the polynomial only has to be large on 1-inputs, not close to 1.
\(\mathrm{sdeg}(f)\) Sign degree
sdeg
Least degree of a polynomial whose sign agrees with f everywhere.
\(\mathrm{rdeg}(f)\) Rational degree
rdeg
\(\varepsilon\) Least d such that f = p/q on the domain with deg(p), deg(q) <= d.
\(\mathrm{rdeg}_{\varepsilon}(f)\) Approximate rational degree
ardeg
\(\varepsilon\) Bounded-error version of rational degree; equals post-selected bounded-error quantum query complexity.
\(\mathrm{ndeg}(f)\) Nondeterministic degree
ndeg
Least degree of a polynomial that is nonzero exactly on the 1-inputs.
\(\deg_2(f)\) Mod-2 degree
deg2
Degree of f as a multilinear polynomial over F_2.
\(\deg_p(f)\) Mod-p degree
degp
\(p\) Degree over F_p.
\(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree
cjdeg
\(\varepsilon\) Least d such that f is approximated by a non-negative combination of width-d conjunctions (a conical junta).
\(\overline{\deg}(f)\) Exact bounded polynomial degree
bdeg
Exact degree with the polynomial also constrained to [0,1] on the entire Boolean cube.
\(\overline{\deg}^{\mathrm{cert}}(f)\) Bounded degree certification complexity
degcert
Worst exact bounded degree of a known-input certification promise; a new lower bound on zero-error quantum queries.
\(\overline{\mathrm{osdeg}}^{\,0}_{\varepsilon}(f)\) Bounded polynomial degree with error on 0-inputs
osdeg0
\(\varepsilon\) A polynomial bounded in [0,1], exact on 1-inputs and approximate on 0-inputs.
\(\overline{\mathrm{osdeg}}^{\,1}_{\varepsilon}(f)\) Bounded polynomial degree with error on 1-inputs
osdeg1
\(\varepsilon\) A polynomial bounded in [0,1], exact on 0-inputs and approximate on 1-inputs.
\(\overline{\mathrm{osdeg}}_{\varepsilon}(f)\) One-sided-error bounded polynomial degree
osdeg
\(\varepsilon\) The maximum of the two bounded one-sided-error degrees; lower-bounds zero-error quantum queries.

Combinatorial

Sensitivity, block sensitivity, certificates, spectral sensitivity.

SymbolName totalpartialrelation Parameters What it is
\(\mathrm{s}(f)\) Sensitivity
s
Max over inputs of the number of coordinates whose flip changes the output.
\(\mathrm{s}^0(f)\) 0-sensitivity
s0
Sensitivity maximised only over 0-inputs.
\(\mathrm{s}^1(f)\) 1-sensitivity
s1
Sensitivity maximised only over 1-inputs.
\(\mathrm{bs}(f)\) Block sensitivity
bs
Max number of disjoint blocks of coordinates each of whose flips changes the output.
\(\mathrm{bs}^0(f)\) 0-block sensitivity
bs0
Block sensitivity maximised only over 0-inputs.
\(\mathrm{bs}^1(f)\) 1-block sensitivity
bs1
Block sensitivity maximised only over 1-inputs.
\(\mathrm{fbs}(f)\) Fractional block sensitivity
fbs
LP relaxation of block sensitivity; equals the LP relaxation of certificate complexity by duality.
\(\mathrm{FC}(f)\) Fractional certificate complexity
FC
LP relaxation of certificate complexity: fractional weights on coordinates that must cover every disagreement.
\(\mathrm{cbs}(S)\) Critical block sensitivity
cbs
Block sensitivity of a search problem: the adversary picks the input, but the algorithm picks which valid answer to commit to.
\(\lambda(f)\) Spectral sensitivity
lambda
Largest eigenvalue of the adjacency matrix of the sensitivity graph of f.
\(\mathrm{C}(f)\) Certificate complexity
C
Max over inputs of the smallest partial assignment that fixes the value of f.
\(\mathrm{C}^0(f)\) 0-certificate complexity
C0
Largest minimal certificate over 0-inputs; the co-nondeterministic query complexity.
\(\mathrm{C}^1(f)\) 1-certificate complexity
C1
Largest minimal certificate over 1-inputs; the nondeterministic query complexity.
\(\mathrm{C}_{\min}(f)\) Minimum certificate complexity
Cmin
Min (rather than max) over inputs of the smallest certificate.
\(\mathrm{UC}(f)\) Unambiguous certificate complexity
UC
Certificate complexity where the certificates form a partition-like unambiguous cover.
\(\mathrm{UC}_{\min}(f)\) Minimum unambiguous certificate complexity
UCmin
The cheaper of the two one-sided unambiguous certificate complexities.
\(\mathrm{SP}(f)\) Subcube partition complexity
SP
Smallest k such that the cube can be partitioned into monochromatic subcubes of codimension <= k.
\(\lambda^{\mathrm{cert}}(f)\) Spectral sensitivity certification
lambdacert
Spectral sensitivity of the hardest known-input certification promise; exactly the square root of sensitivity.
\(\mathrm{RC}(f)\) Randomized certificate complexity
RC
Cost of a randomized verifier that must detect, with constant probability, that the input has been changed to flip f.
\(\mathrm{EC}(f)\) Expectational certificate complexity
EC
A relaxation of certificate complexity in which the certificate is a distribution and only expected agreement is required.

Fourier-analytic

Influence, noise sensitivity, spectral norm, sparsity.

SymbolName totalpartialrelation Parameters What it is
\(\mathrm{Var}(f)\) Variance
Var
How far f is from constant. Not a complexity measure -- the unit the other Fourier quantities are divided by.
\(\mathrm{I}(f)\) Total influence (L2 influence)
Inf
Expected number of sensitive coordinates on a uniformly random input; equals sum_S |S| fhat(S)^2.
\(\mathrm{I}^{1}(f)\) Total L1 influence
Inf1
Sum over i of E_x |D_i f(x)|; differs from total influence for bounded real-valued f.
\(\mathrm{MaxInf}(f)\) Maximum influence
MaxInf
The largest single-coordinate influence.
\(\mathrm{osss}(f)\) OSSS number
osss
Var(f)/MaxInf(f): the query lower bound the OSSS inequality reads off the influences.
\(\mathrm{NS}_{\delta}(f)\) Noise sensitivity
NS
\(\delta\) Probability that f changes when each bit is flipped independently with probability delta.
\(\mathrm{Stab}_{\rho}(f)\) Noise stability
Stab
\(\rho\) Correlation of f(x) and f(y) for rho-correlated x,y.
\(\mathrm{nsr}(f)\) Noise robustness
nsr
One over the noise rate at which f starts to break: the query-scale reading of NS_delta.
\(\hat{L}_1(f)\) Spectral norm
L1
\(\varepsilon\) Sum of absolute values of the Fourier coefficients.
\(\mathrm{spar}(f)\) Fourier sparsity
spar
Number of nonzero Fourier coefficients.
\(\dim_{\mathbb{F}_2}(f)\) Fourier dimension
Fdim
Dimension of the F_2-span of the Fourier support.

Adversary & games

Quantum and classical adversary bounds, certificate games.

SymbolName totalpartialrelation Parameters What it is
\(\mathrm{CA}(f)\) Classical adversary bound
CA
The classical analogue of the positive-weights quantum adversary; a lower bound on R.
\(\mathrm{Adv}(f)\) Positive-weights adversary bound
Adv
The original quantum adversary lower bound; all positive-weight variants coincide.
\(\mathrm{CG}(f)\) Certificate game complexity (private coin)
CG
Inverse winning probability of a zero-communication game where two players must agree on a coordinate where their inputs differ.
\(\mathrm{CG}^{\mathrm{pub}}(f)\) Certificate game complexity (public coin)
CGpub
Public-coin version of the certificate game; equals the classical adversary bound.
\(\mathrm{CG}^{*}(f)\) Quantum certificate game complexity
CGstar
Certificate game with shared entanglement.
\(\mathrm{CG}^{\mathrm{ns}}(f)\) Non-signaling certificate game complexity
CGns
Certificate game with arbitrary non-signaling correlations; the weakest of the four.
\(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound
Advpm
The tight SDP characterisation of bounded-error quantum query complexity.
\(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm
gamma2
Factorisation-norm formulation of the general adversary bound.
\(\mathrm{MAdv}(f)\) Multiplicative adversary
MAdv
A multiplicative-weight version of the adversary method, at least as strong as Adv^pm.
\(\mathrm{prt}_{\varepsilon}(f)\) Partition bound
prt
\(\varepsilon\) LP relaxation of "cover the cube by few low-codimension monochromatic subcubes"; subsumes most classical lower bound techniques.
\(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound
rprt
\(\varepsilon\) The partition bound with the "fires with probability exactly 1" constraint relaxed to "at most 1"; weaker, but unlike prt it lower-bounds information complexity.

Composition-theoretic

Measures invented to make R(f o g) behave: RS, chi, chibar, LR, noisyR, R*.

SymbolName totalpartialrelation Parameters What it is
\(\mathrm{RS}(f)\) Sabotage complexity
RS
Randomized cost of finding a "sabotaged" (damaged) input bit; the first measure with perfect composition.
\(\chi(f)\) Conflict complexity
chi
A measure of how hard it is for a decision tree to distinguish a random 0-input from a random 1-input, one query at a time.
\(\bar{\chi}(f)\) Max-conflict complexity
chibar
A strengthening of conflict complexity that dominates sabotage complexity.
\(\mathrm{LR}(f)\) Linearised randomized complexity
LR
The largest measure satisfying an inner composition theorem R(f o g) = Omega(R(f) LR(g)).
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity
noisyR
Randomized complexity when the algorithm may buy a biased (noisy) copy of any bit at cost proportional to bias squared.
\(\mathrm{noisyR}^{\mathrm{na}}(f)\) Non-adaptive noisy randomized query complexity
noisyRna
The bias-purchasing model with the whole schedule of biases committed to in advance.
\(\mathrm{Corr}_{\varepsilon}(f)\) Correlated samples complexity
Corr
\(\varepsilon\) Distributional complexity when the algorithm may query as many independent samples from the same side as it likes.
\(\mathrm{Sel}_{\varepsilon}(f)\) Selection complexity
Sel
\(\varepsilon\) Cost of solving any one of k independent instances, with k chosen by the algorithm and the instances drawn from the hardest distribution.
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate
Rstar
lim_k R(f^{o k})^{1/k}: the per-level cost of composing f with itself many times.