Q The Query Complexity Zoo
\(\mathrm{LR}(f)\)

Linearised randomized complexity

The largest measure satisfying an inner composition theorem R(f o g) = Omega(R(f) LR(g)).

Definition

Where $\mathrm{R}$ effectively charges $1/\gamma^2$ for an algorithm that achieves bias $\gamma$ towards the right answer, $\mathrm{LR}$ charges only $1/\gamma$ -- it linearises the cost in the bias. Consequently $\mathrm{LR}(f)$ can be as small as $\sqrt{\mathrm{R}(f)}$ and never larger than $\mathrm{R}(f)$.

Ben-David-Blais-Göös-Maystre prove it is exactly the right inner measure: $\mathrm{R}(f\circ g)=\Omega(\mathrm{R}(f)\mathrm{LR}(g))$ for all partial $f,g$, and no larger measure has this property.

Basic facts

  • $\Omega(\sqrt{\mathrm{R}(f)}) \le \mathrm{LR}(f) \le \mathrm{R}(f)$.
  • $\mathrm{LR}$ can be polynomially larger than $\bar{\chi}$ [BBGM22].
  • $\mathrm{R}^*(f) \ge \Omega(\mathrm{LR}(f))$.
  • Total functions have $\mathrm{R}/\mathrm{LR}=\Omega(\log N)$ and $\mathrm{LR}/\bar\chi=\Omega(\sqrt{\log N})$ [Meiburg26composition]; see \(M_q\) and \(G_q\).

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{LR}(f)\). “\(\mathrm{LR}(f)\) in terms of it” is the pair with \(\mathrm{LR}(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{LR}(f)\) in terms of it It in terms of \(\mathrm{LR}(f)\)
\(\bar{\chi}(f)\) Max-conflict complexity total1,2 partial1,2 open pair → total1,1 partial1,1 open pair →
\(\mathrm{RS}(f)\) Sabotage complexity total1,2 partial∞ derived open pair → total1,1 partial1,1 derived open pair →
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total1,1 partial1,1 open pair → total1,2 partial1,2 open pair →
\(\mathrm{R}^{*}(f)\) Asymptotic composition rate total1,1 partial1,? open pair → total1,2 partial1,2 derived open pair →
\(\mathrm{noisyR}(f)\) Noisy randomized query complexity total1,3 partialexp,? derived open pair → total1,2 partial1,2 derived open pair →

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

Known values

FunctionValueNotes
OR total \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
AND total \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
PARITY total \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
MAJORITY total \(\Theta(n)\) Sandwiched: $\mathrm{RS}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with $\mathrm{RS}(f) = \Theta(n)$ and $\mathrm{D}(f) = n$ here.
Threshold total \(\Theta(n)\) Squeezed: $\bar{\chi}(f) = O(\mathrm{LR}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(n)$. BBGM22
Symmetric functions (general) total \(\Theta(n)\) Sandwiched: $\bar{\chi}(f) = O(\mathrm{LR}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(n)$ here. BBGM22
EXACT-HALF total \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
ODD-MAX-BIT total \(\Theta(n)\) Sandwiched: $\bar{\chi}(f) = O(\mathrm{LR}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(n)$ here. BBGM22
ADDRESS / multiplexer total \(\Theta(k+1)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with both ends $k+1$ here.
Binary tree navigation total \(\Theta(k)\) Sandwiched: $\bar{\chi}(f) = O(\mathrm{LR}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(k)$ here. BBGM22
TRIBES total \(\Theta(n)\) Sandwiched: $\bar{\chi}(f) = O(\mathrm{LR}(f)) \le \mathrm{R}(f)$, with both ends $\Theta(n)$ here. BBGM22
AND-OR tree (depth 2) total \(\Theta(n^2)\) Theorem 9.1; for LR use max-conflict ≤ O(LR) ≤ O(R). The conflict bound is the theorem’s bracket, not the stronger introduction-table upper bound. Meiburg26composition
NAND tree (balanced AND-OR formula) total \(\Omega(\sqrt N),\ O\!\big(N^{\,0.753\ldots}\big)\) $\Omega(\sqrt{\mathrm{R}}) \le \mathrm{LR} \le \mathrm{R}$ [BBGM22] gives $\Omega(N^{0.377})$, which the stronger $\mathrm{LR} = \Omega(\bar\chi) = \Omega(\mathrm{bs}) = \Omega(\sqrt N)$ improves. Note that $\mathrm{R}$ is multiplicative along this family ($f_d\circ f_e = f_{d+e}$), so the composition theorem $\mathrm{R}(F\circ f_d^m) = \Omega(\mathrm{R}(F)\mathrm{LR}(f_d))$ is tight for these gadgets only if $\mathrm{LR}$ sits at the top of this window. BBGM22
Recursive MAJORITY-of-3 total \(\Omega(2^{\,d}),\ O(2.64944^{\,d})\) $\mathrm{LR} = \Omega(\bar\chi) = \Omega(\mathrm{bs}) = \Omega(2^d)$ and $\mathrm{LR} \le \mathrm{R}$ [BBGM22]; the generic $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}})$ is weaker here. BBGM22
Kushilevitz's function (iterated) total \(\Theta(N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with both ends $N$ here.
Rubinstein's function total \(\Theta(N)\) $\mathrm{LR} = \Omega(\bar\chi) = \Omega(\mathrm{bs}) = \Omega(N)$ and $\mathrm{LR} \le \mathrm{R} = O(N)$ [BBGM22]. So this gadget loses nothing as the inner function of a composition, despite the extreme $\mathrm{s}$-vs-$\mathrm{bs}$ gap. BBGM22
Ambainis-Sun function total \(\Theta(N)\) $\mathrm{LR} = \Omega(\bar\chi) = \Omega(\mathrm{bs}) = \Omega(N)$ and $\mathrm{LR} \le \mathrm{R} = O(N)$ [BBGM22]: the extremal $\mathrm{s}$-vs-$\mathrm{bs}$ gadget is nonetheless a perfect inner function for composition. BBGM22
AND composed with NOT-EXACT-HALF total \(\Theta(n^2)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n^2)$ here.
Meiburg's tournament-subcube function total \(\Omega(14011^{\,d})\) putative $\mathrm{LR} = \Omega(\bar\chi) = \Omega(\mathrm{bs}) = \Omega(14011^{\,d})$ [BBGM22]. Since $\mathrm{LR} \le \mathrm{R}$ and $\mathrm{R} \ge \mathrm{bs}$ is all that is known, the two lower bounds coincide. BBGM22
Pointer functions total \(\widetilde\Theta(\sqrt n)\) Variant $f_{2m,m}$: squeezed between $\bar\chi=\widetilde\Theta(\sqrt n)$ and $\mathrm{R}=\widetilde O(\sqrt n)$.
Cheat-sheet functions total \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) Squeezed between $\bar\chi$ and $\mathrm{R}$, neither of which is pinned here; also $\mathrm{LR}=\Omega(\sqrt{\mathrm{R}})=\widetilde\Omega(\sqrt n)$ directly.
Low-sensitivity function from unambiguous certificates total \(\widetilde\Omega(n^{3/2})\) Squeeze: $\mathrm{LR}\ge\bar\chi=\widetilde\Omega(n^{3/2})$, equivalently $\mathrm{LR}=\Omega(\sqrt{\mathrm{R}})$.
Unambiguous-DNF / Alon-Saks-Seymour function total \(\widetilde\Omega(n^{4/3}),\ \widetilde O(n^2)\) Squeezed between $\bar\chi=\widetilde\Omega(n^{4/3})$ and $\mathrm{R}=\widetilde O(n^2)$.
Gilmer-Saks-Srinivasan functions total \(\Omega(n),\ O(n^2)\) Squeezed between $\bar\chi=\Omega(n)$ and $\mathrm{R}=O(n^2)$.
Goos-Pitassi-Watson partition-number function total \(\widetilde\Omega(\sqrt n),\ \widetilde O(n)\) Squeezed between $\bar\chi=\widetilde\Omega(\sqrt n)$ and $\mathrm{R}=\widetilde O(n)$.
Goos-Jayram-Pitassi-Watson function total \(\widetilde\Omega(n^{1/3}),\ \widetilde O(n^{2/3})\) Squeezed between $\bar\chi$ and $\mathrm{R}$; the direct floor $\mathrm{LR}=\Omega(\sqrt{\mathrm{R}})$ gives the same $\widetilde\Omega(n^{1/3})$.
Ambainis' exact-quantum function total \(\Theta(3^d)\) Squeeze: $\bar\chi=O(\mathrm{LR})$ and $\mathrm{LR}=O(\mathrm{R}^{*})\le\mathrm{R}$ [BBGM22]; both ends are $3^d$. This is the $\mathrm{LR}=\Theta(\mathrm{R})$ end of the range, as the recorded $\mathrm{RS}=\Theta(\mathrm{R})$ forces. BBGM22
FORRELATION partial \(\widetilde\Omega(n^{1/4})\) $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}})$ for every partial $f$, and $\mathrm{R} = \widetilde\Theta(\sqrt n)$; the upper end is $\mathrm{LR} \le \mathrm{R}$. Even the linearised measure, which charges $1/\gamma$ instead of $1/\gamma^2$ for bias $\gamma$, stays polynomially above $\mathrm{Q} = 1$.
k-FORRELATION partial \(\widetilde\Omega\!\big(n^{1/2-1/(2k)}\big)\) $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}})$ for every partial $f$; the upper end is $\mathrm{LR} \le \mathrm{R}$.
Simon's problem partial \(\Omega(2^{n/4})\) $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}})$ for every partial $f$, and $\mathrm{LR} \le \mathrm{R} = \Theta(2^{n/2})$.
Deutsch-Jozsa partial \(\Theta(1)\) Sandwiched: $\Omega(\sqrt{\mathrm{R}}) \le \mathrm{LR} \le \mathrm{R} = O(1)$.
Bernstein-Vazirani partial \(\Omega(\sqrt n)\) $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}})$ and $\mathrm{LR} \le \mathrm{R} = \Theta(n)$; the true value is not pinned down here.
Gap-Majority partial \(\Theta\!\big(\sqrt{\mathrm{R}}\big) = \Theta\!\big(\min(\sqrt n, 1/\delta)\big)\)· The extreme case of the $\Omega(\sqrt{\mathrm{R}}) \le \mathrm{LR} \le \mathrm{R}$ sandwich, and the reason the measure was introduced: a single query already gives bias $\Theta(\delta)$ towards the answer, and $\mathrm{LR}$ charges $1/\gamma$ rather than $1/\gamma^2$ for bias $\gamma$. So gapped majority is cheap for $\mathrm{LR}$ and expensive for $\mathrm{R}$, which is exactly the slack that makes randomized composition fail. BBGM22
Gap-Majority at constant gap partial \(\Theta(1)\)· $\Omega(\sqrt{\mathrm{R}}) \le \mathrm{LR} \le \mathrm{R}$, and both ends are constant. BBGM22
Approximate index partial \(\Omega\big((k\log k)^{1/4}\big)\) $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}})$, and $\mathrm{LR} \le \mathrm{R} = O(\sqrt{k\log k})$. Do not confuse this with \(\mathrm{noisyR}(f)\) $= O(\log k)$: $\mathrm{LR}$ charges $1/\gamma$ for bias $\gamma$ and $\mathrm{noisyR}$ charges $\gamma^2$, so only the latter makes cheap guessing cheap.
Collision problem partial \(\Omega(n^{1/4})\) $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}})$ and $\mathrm{LR} \le \mathrm{R} = O(\sqrt n)$.
Element distinctness total \(\Theta(n)\) Between $\bar\chi = \Theta(n)$ and $\mathrm{R} = \Theta(n)$. Element distinctness composes perfectly on the randomized side, unlike the partial functions above where $\mathrm{LR}$ can drop to $\sqrt{\mathrm{R}}$.
Ambainis-Belovs function partial \(\Omega(n^{1/6})\) $\mathrm{LR} = \Omega(\sqrt{\mathrm{R}}) = \Omega(n^{1/6})$, with $\mathrm{LR} \le \mathrm{R} = O(n)$ above. BBGM22
Surjectivity total \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with both ends $\Theta(n)$ here. The lower end of this sandwich is itself the zoo's own argument (see the note on $\mathrm{s}$), so this value inherits its status.
$k$-distinctness total \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(n)$ here.
Triangle finding total \(\Theta(m^2) = \Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{R}_{\varepsilon}(f)$, with both ends $\Theta(m^2) = \Theta(n)$ here.
Recursive Fourier sampling partial \(n^{\Omega(\log n)} \text{ at } \ell = \log n\) $\mathrm{LR}(f)=\Omega(\sqrt{\mathrm{R}(f)})$ and $\mathrm{LR}(f)\le\mathrm{R}(f)$ (\(\mathrm{LR}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\), both for partial $f$) [BBGM22]. A square root does not dent $n^{\Omega(\log n)}$, so the linearised measure is superpolynomial too; capped above by $\mathrm{D}=O(n^{\ell})$. BBGM22
Ordered search partial \(\Theta(\log n)\) $\mathrm{LR}\le\mathrm{R}=O(\log n)$ [BBGM22], and $\bar\chi=O(\mathrm{LR})$ with $\bar\chi=\Theta(\log n)$ gives the matching lower bound. So the linearised measure does not see the $\sqrt{\mathrm{R}}$ slack here: ordered search composes perfectly. BBGM22 GLSS19
Inner product mod 2 total \(\Theta(n)\) Sandwiched: $\mathrm{s}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with both ends $n$ here.
Minsky-Papert one-in-a-box total \(\Theta(m^3) = \Theta(N)\) Sandwiched between $\bar\chi = \Theta(m^3)$ and $\mathrm{R} = \Theta(m^3)$. The inner composition measure loses nothing on a read-once AND-OR tree.
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) Sandwiched: $\mathrm{bs}(f) \le \mathrm{LR}(f) \le \mathrm{D}(f)$, with both ends $\Theta(m) = \Theta(\sqrt N)$ here.
Scorpion graphs total \(\Theta(m)\) Squeezed between $\bar\chi = \Theta(m)$ and $\mathrm{R} = \Theta(m)$.
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) Squeezed between $\bar\chi = \Theta(m^2)$ and $\mathrm{R} = \Theta(m^2)$.
Meiburg’s parity-pointer family total \(\Theta(q^3\log^2 q)\) Meiburg26composition
Meiburg’s majority-pointer family total \(O(q^3\log q)\) Meiburg26composition
Meiburg’s parity-masked majority family total \(\Omega(q^3\log^{3/2}q),\ O(q^3\log^2q)\) Meiburg26composition