Q The Query Complexity Zoo
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\)

Distributional query complexity

Least depth of a deterministic tree that is correct except with probability eps under the input distribution mu.

Definition

Fix a distribution $\mu$ on the domain. $\mathrm{D}^\mu_\varepsilon(f)$ is the smallest depth of a deterministic decision tree $T$ with $\Pr_{x\sim\mu}[T(x)\ne f(x)] \le \varepsilon$. Yao's minimax principle: $\mathrm{R}_\varepsilon(f) = \max_\mu \mathrm{D}^\mu_\varepsilon(f)$ (for the worst-case-cost version; see Yao's minimax and its failures for the subtleties with the expected-cost version $\bar{\mathrm{R}}_\varepsilon$).

Parameters

\(\mu\) (mu) default \(worst case\)

input distribution

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{D}^{\mu}_{\varepsilon}(f)\). “\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) in terms of it” is the pair with \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.

Other measure \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) in terms of it It in terms of \(\mathrm{D}^{\mu}_{\varepsilon}(f)\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total1,1 partial1,1 relation1,1 open pair → total1,1 partial1,1 relation1,1 derived open pair →
\(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity total1,1 partial1,1 relation1,1 derived open pair → total1,1 partial1,1 relation1,1 open pair →
\(\mathrm{D}^{\mathrm{prod}}(f)\) Product-distribution distributional complexity total1.08,? partial∞ relation∞ derived open pair → total1,1 partial1,1 relation1,1 derived open pair →
\(\mathrm{D}(f)\) Deterministic query complexity total1,1 partial1,1 relation1,1 derived open pair → total2,3 partial∞ relation∞ derived open pair →

The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(\Theta(n)\) By Yao's minimax principle $\max_\mu \mathrm{D}^{\mu}_{1/3}(f) = \mathrm{R}_{1/3}(f) = \Theta(n)$. A concrete maximiser: half the mass on $0^n$, the other half spread uniformly over the $n$ weight-one inputs. A depth-$d$ tree that has seen only zeros is consistent with $0^n$ and with the $n-d$ unqueried $e_i$, so whichever answer it commits to it errs on mass at least $\min\{1/2,\ (n-d)/(2n)\}$, forcing $d \ge n/3$. See \(\mathrm{D}^{\mathrm{prod}}(f)\) for the product-distribution version. Yao77
AND total \(\min\{n,\ \lceil \log(1/\varepsilon)/\log(1/p)\rceil\} \text{ under } \mu_p\) The cleanest illustration of why $\mathrm{D}^{\mu}$ is a family of measures rather than one number. Let $\mu_p$ make each bit $1$ independently with probability $p$. Querying bits until one comes up $0$ and answering $1$ if the first $m$ are all $1$ errs with probability $p^{m}(1-p^{n-m})$, so $m = \lceil \log(1/\varepsilon)/\log(1/p)\rceil$ queries suffice; conversely, the leaf reached by the all-ones input has some depth $m_0 \le m$ and carries $\mathrm{AND}^{-1}(0)$-mass $p^{m_0} - p^{n}$ against $\mathrm{AND}^{-1}(1)$-mass $p^{n}$, so the error is at least $\min\{p^{m}-p^{n},\,p^{n}\}$. At $p = 1/2$ this is $\Theta(\log(1/\varepsilon))$; at $p = 1 - 1/n$ it is $n$. Averaging over the parameter is exactly what the zoo cannot do, which is why $\mathrm{D}^{\mu}$ is left out of the ladder ordering on the matrix page.
PARITY total \(n\) Under the uniform $\mu$, for every $\varepsilon < 1/2$ -- and since $\mathrm{D}^\mu \le \mathrm{D} = n$ for every $\mu$, the uniform distribution is simultaneously the hardest one, so no choice of $\mu$ has to be recorded alongside the value. Every leaf of a tree of depth $< n$ leaves some coordinate unqueried, and conditioned on the queried bits the parity is still uniform on $\{0,1\}$; so any such tree errs with probability exactly $1/2$ under the uniform distribution. This is the extreme point of Yao's principle: one distribution already witnesses the worst case, with no slack.
MAJORITY total \(\Theta(n)\) Yao's minimax gives $\max_\mu \mathrm{D}^{\mu}_{1/3}(f) = \mathrm{R}_{1/3}(f) = \Theta(n)$, and the \(\mathrm{D}^{\mathrm{prod}}(f)\) line shows the uniform product distribution already attains it: after $o(n)$ queries the unseen coordinates leave the majority undecided with constant probability. Yao77
Threshold total \(\Theta(n)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3}(f) = \mathrm{R}_{1/3}(f) = \Theta(n)$, uniformly in $k$ by the \(\mathrm{R}_{\varepsilon}(f)\) line, and the \(\mathrm{D}^{\mathrm{prod}}(f)\) line exhibits a product distribution attaining it. Yao77
Symmetric functions (general) total \(\Theta(n)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3}(f) = \mathrm{R}_{1/3}(f) = \Theta(n)$ for every non-constant symmetric $f$, by the \(\mathrm{R}_{\varepsilon}(f)\) line; the \(\mathrm{D}^{\mathrm{prod}}(f)\) line exhibits a product distribution that attains it. Yao77
EXACT-HALF total \(\Theta(n)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3}(f) = \mathrm{R}_{1/3}(f) = \Theta(n)$; the \(\mathrm{D}^{\mathrm{prod}}(f)\) line shows the uniform distribution already attains it. Yao77
ODD-MAX-BIT total \(\Theta(n)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3}(f) = \mathrm{R}_{1/3}(f) = \Theta(n)$; the \(\mathrm{D}^{\mathrm{prod}}(f)\) line exhibits a product distribution attaining it. Yao77
ADDRESS / multiplexer total \(\Theta(k)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3}(f) = \mathrm{R}_{1/3}(f) = \Theta(k)$; the \(\mathrm{D}^{\mathrm{prod}}(f)\) line shows the uniform distribution attains it. Yao77
Binary tree navigation total \(\Theta(k)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3}(f) = \mathrm{R}_{1/3}(f) = \Theta(k)$, and the \(\mathrm{D}^{\mathrm{prod}}(f)\) line shows the uniform distribution already forces the full depth $k$. Yao77
TRIBES total \(\Theta(n)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3}(f) = \mathrm{R}_{1/3}(f) = \Theta(n)$. Worth contrasting with the \(\mathrm{D}^{\mathrm{prod}}(f)\) line, $\Theta(n/\log n)$: no product distribution is hard enough, so the maximising $\mu$ must correlate the variables inside a tribe. Yao77
AND-OR tree (depth 2) total \(\Theta(n^2)\) Yao's minimax principle for worst-case cost: $\max_\mu \mathrm{D}^{\mu}_{1/3} = \Theta(\mathrm{R}_{1/3})$, and $\mathrm{R} = \Theta(n^2)$ here, so no distribution is harder than $\Theta(N)$ and some distribution is that hard. Yao77
NAND tree (balanced AND-OR formula) total \(\Theta\!\big(N^{\,0.753\ldots}\big)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3} = \Theta(\mathrm{R}_{1/3})$. Both directions of the recorded $\mathrm{R} = \Theta(N^{0.753\ldots})$ are in fact proved distributionally -- Saks-Wigderson's lower bound exhibits an explicit recursive $\mu$ -- so the distributional value is the same $N^{\log_2((1+\sqrt{33})/4)}$. Yao77 SaksWigderson86
Recursive MAJORITY-of-3 total \(\ge (\tfrac12 - \delta)\,2.57143^{\,d}\) The lower bound is proved against an explicit hard distribution, so it is a statement about $\mathrm{D}^{\mu}_{\delta}$; Yao's principle then transfers it to $\mathrm{R}_\delta$. Goos-Jayram's later $\Omega(2.59^d)$ goes through conical juntas instead and is not of this form. MNSSTX16
Kushilevitz's function (iterated) total \(\Theta(N)\) Yao's minimax gives $\max_\mu \mathrm{D}^{\mu}_{1/3} = \Theta(\mathrm{R}_{1/3}) = \Theta(N)$. Yao77
Rubinstein's function total \(\Theta(N)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3} = \Theta(\mathrm{R}_{1/3}) = \Theta(N)$. Yao77
Ambainis-Sun function total \(\Theta(N)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3} = \Theta(\mathrm{R}_{1/3}) = \Theta(N)$. Yao77
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3} = \Theta(\mathrm{R}_{1/3}) = \Theta(n^2)$. Yao77
Meiburg's tournament-subcube function total \(\ge 14011^{\,d}\) putative Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{1/3} = \Theta(\mathrm{R}_{1/3})$, and $\mathrm{R} \ge \mathrm{bs} \ge 14011^{\,d}$. Yao77
Pointer functions total \(\widetilde O(\sqrt n)\) Variant $g_{m,m}$: $\max_\mu\mathrm{D}^{\mu}=\Theta(\mathrm{R})=\widetilde O(\sqrt n)$ by Yao's minimax.
Cheat-sheet functions total \(\widetilde\Theta(n)\) Maximised over input distributions: Yao's minimax gives $\max_\mu\mathrm{D}^{\mu}=\Theta(\mathrm{R})$.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^3)\) Yao's minimax: $\max_\mu\mathrm{D}^{\mu}=\Theta(\mathrm{R})=\widetilde\Omega(n^3)$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{4/3})\) Yao's minimax: $\max_\mu\mathrm{D}^{\mu}=\Theta(\mathrm{R})=\widetilde\Omega(n^{4/3})$.
Gilmer-Saks-Srinivasan functions total \(\Omega(n)\) Yao's minimax: $\max_\mu\mathrm{D}^{\mu}=\Theta(\mathrm{R})=\Omega(n)$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(\sqrt n)\) Yao's minimax: $\max_\mu\mathrm{D}^{\mu}=\Theta(\mathrm{R})=\widetilde\Omega(\sqrt n)$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Theta(n^{2/3})\) Maximised over input distributions: Yao's minimax gives $\max_\mu \mathrm{D}^{\mu}=\Theta(\mathrm{R})$.
Ambainis' exact-quantum function total \(\Theta(3^d)\) Maximised over input distributions: Yao's minimax gives $\max_\mu\mathrm{D}^{\mu}=\Theta(\mathrm{R})$.
FORRELATION partial \(\widetilde\Theta(\sqrt n)\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \widetilde\Theta(\sqrt n)$.
k-FORRELATION partial \(\widetilde\Theta\!\big(n^{1-1/k}\big)\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R}$.
Simon's problem partial \(\Theta(2^{n/2})\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \Theta(2^{n/2})$.
Deutsch-Jozsa partial \(\Theta(1)\) Sandwiched between $\mathrm{Q}$ and $\mathrm{R} = O(1)$.
Bernstein-Vazirani partial \(\Theta(n)\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \Theta(n)$.
Marked bit partial \(\Theta(n)\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon$; the planted-mark distribution above is the maximiser.
Dense marked bit partial \(\Theta(1)\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon = \Theta(1)$.
Unstructured search (relation) relation \(\Theta(n)\) Yao's minimax: $\max_\mu \mathrm{D}^{\mu}_{\varepsilon} = \mathrm{R}_{\varepsilon} = \Theta(n)$.
FIND-1 under a density promise relation \(\Theta(1)\) Sandwiched between $\mathrm{Q}$ and $\mathrm{R} = O(1)$.
Approximate Hamming weight relation \(\Theta(1)\) Sandwiched: $\mathrm{D}_\mu \le \mathrm{R} = \Theta(1)$ for every $\mu$.
SearchCNF relation \(\Theta(1)\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \Theta(1)$.
Gap-Majority partial \(\Theta(\min(n, 1/\delta^2))\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R}$.
Gap-Majority at constant gap partial \(\Theta(1)\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R}$.
Parity-labelled FIND-1 partial \(\Theta(1)\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \Theta(1)$.
Approximate index partial \(\Theta(\sqrt{k\log k})\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R}$.
Collision problem partial \(\Theta(\sqrt n)\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \Theta(\sqrt n)$.
Element distinctness total \(\Theta(n)\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \Theta(n)$.
Ambainis-Belovs function partial \(\Omega(n^{1/3})\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \Omega(n^{1/3})$.
Ben-David-Kundu total search problems relation \(\widetilde\Omega(\sqrt n)\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \widetilde\Omega(\sqrt n)$; the uniform distribution already achieves it -- see \(\mathrm{D}^{\mathrm{prod}}(f)\).
Yamakawa-Zhandry problem relation \(2^{\Omega(n)}\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon = 2^{\Omega(n)}$.
Surjectivity total \(\Theta(n)\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon = \Theta(n)$.
$k$-distinctness total \(\Theta(n)\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon = \Theta(n)$.
Triangle finding total \(\Theta(m^2) = \Theta(n)\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon = \Theta(m^2)$.
Recursive Fourier sampling partial \(n^{\Omega(\log n)} \text{ at } \ell = \log n\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon$; and this is the form the bound is actually proved in -- [BernsteinVazirani97, Thm. 8.4.6] argues against a uniformly random legal oracle, so it is a $\mathrm{D}^\mu$ statement first and an $\mathrm{R}$ statement afterwards. BernsteinVazirani97
Welded trees relation \(\tilde\Theta(2^{n/2})\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon = \tilde\Theta(2^{n/2})$; the maximising $\mu$ is the uniform distribution over welded trees, namings and colourings, which is exactly what the lower-bound proofs use.
Local search on the hypercube relation \(\Theta(2^{n/2}\sqrt n)\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon = \Theta(2^{n/2}\sqrt n)$. [Aldous83] and [Zhang09localsearch] both argue against an explicit $\mu$ -- a random-walk / staircase distribution -- so the lower bound is really a $\mathrm{D}^\mu$ bound to begin with.
Local search on the grid relation \(\Theta(k^{d/2})\ (d \ge 4)\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon$; [Zhang09localsearch, Thm. 3] argues against an explicit random-walk distribution, so the bound is a $\mathrm{D}^\mu$ bound already.
Fourier fishing relation \(\Omega(N/\log N),\ O(N)\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon$. The maximising $\mu$ is the uniform distribution on truth tables: [AaronsonChen17, Thm. 6.4] proves its bound against a uniformly random $f$, so the statement is a $\mathrm{D}^\mu$ statement before it is an $\mathrm{R}$ statement.
Ordered search partial \(\Theta(\log n)\) By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon$, and the maximising $\mu$ is the uniform distribution on the $n+1$ promise inputs -- which is exactly the distribution the $\mathrm{R}$ entry's leaf-counting argument uses.
Tseitin search on an expander relation \(\Theta(n)\) By Yao, $\max_\mu \mathrm{D}^\mu = \mathrm{R} = \Theta(n)$.
Inner product mod 2 total \(\Theta(n)\) Worst case over $\mu$: Yao's minimax gives $\max_\mu \mathrm{D}^{\mu}_{\varepsilon}(f) = \mathrm{R}_{\varepsilon}(f) = \Theta(n)$. Yao77
Minsky-Papert one-in-a-box total \(\Theta(m^3) = \Theta(N)\) Worst case over $\mu$: Yao's minimax gives $\max_\mu \mathrm{D}^{\mu}_{\varepsilon}(f) = \mathrm{R}_{\varepsilon}(f) = \Theta(N)$. Yao77
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) Worst case over $\mu$: Yao's minimax gives $\max_\mu \mathrm{D}^{\mu}_{\varepsilon}(f) = \mathrm{R}_{\varepsilon}(f) = \Theta(m)$. Yao77
Scorpion graphs total \(\Theta(m)\) Worst case over $\mu$: Yao's minimax gives $\max_\mu \mathrm{D}^{\mu}_{\varepsilon}(f) = \mathrm{R}_{\varepsilon}(f) = \Theta(m)$. Yao77
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) Worst case over $\mu$: Yao's minimax gives $\max_\mu \mathrm{D}^{\mu}_{\varepsilon}(f) = \mathrm{R}_{\varepsilon}(f) = \Theta(m^2)$. Yao77