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.
| Symbol | Name | total | partial | relation | 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.
| Symbol | Name | total | partial | relation | 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.
| Symbol | Name | total | partial | relation | 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.
| Symbol | Name | total | partial | relation | 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.
| Symbol | Name | total | partial | relation | 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.
| Symbol | Name | total | partial | relation | 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.
| Symbol | Name | total | partial | relation | 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*.
| Symbol | Name | total | partial | relation | 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. |