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
\(\varepsilon\) (eps) default \(1/3\)
Detailed records:
param-minimax · \(\text{Yao minimax: } \bar{\mathrm{R}}_\varepsilon(f) = \Theta\big(\max_\mu \mathrm{D}^{\mu}_{\varepsilon}(f)\big)\)
\(\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.
The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.
Known values
| Function | Value | Notes |
|---|---|---|
| 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 |