Q The Query Complexity Zoo

Composition

Does M(f o g) = M(f) M(g)? The answer distinguishes the well-behaved measures from the rest, and has spawned a family of measures of its own.

For $f$ on $n$ bits and $g$ on $m$ bits, $f\circ g^n$ is the function on $nm$ bits obtained by feeding $n$ disjoint copies of $g$ into $f$.

Scoreboard

measure composes? reference
$\mathrm{D}$ exactly, even for an outer relation [Savicky02, Tal13, Montanaro14]
$\deg$ exactly [Tal13]
$\mathrm{Q}$ up to constants, even for partial $f,g$ [LMRSS11, Reichardt11]
$\mathrm{Adv}^{\pm}$ exactly (SDP) [HLS07]
$\mathrm{RS}$ perfect lower bound $\mathrm{RS}(f\circ g)\ge\mathrm{RS}(f)\mathrm{RS}(g)$ [BenDavidKothari18]
$\mathrm{R}$ lower bound with $\log(n+1)$ loss, even for partial Boolean $f,g$; constants fail even for total functions [PednekarPodder26STOC, Meiburg26composition]
$\widetilde{\deg}$ up to constants for total Boolean $f,g$ [PednekarPodder26composition, Sherstov12robust]
$\mathrm{Q}_{\mathrm{E}}$ multiplicative lower bound fails on total functions [PednekarPodder26composition, PednekarPodder26STOC]
$\chi$ constant-factor multiplicative lower bound fails on total functions [Meiburg26composition]
$\mathrm{s}$, $\mathrm{bs}$, $\mathrm{C}$ up to constants [Tal13]

Why $\mathrm{R}$ is hard

The natural algorithm for $f\circ g^n$ runs the outer algorithm and amplifies each inner call to error $1/(3\mathrm{R}(f))$, costing $O(\mathrm{R}(f)\mathrm{R}(g)\log \mathrm{R}(f))$. Two things can go wrong with the matching lower bound:

  1. The outer algorithm may tolerate noisy answers from the inner copies, paying less than full price per copy. This is what \(\mathrm{noisyR}(f)\) measures, and $\mathrm{R}(f\circ g^n)=\Omega(\mathrm{noisyR}(f)\mathrm{R}(g))$ is the optimal theorem of that shape.
  2. The outer algorithm may not need a decision from each inner copy, only partial information. This is what \(\chi(f)\), \(\bar{\chi}(f)\), \(\mathrm{RS}(f)\) and \(\mathrm{LR}(f)\) measure, and $\mathrm{R}(f\circ g^n)=\Omega(\mathrm{R}(f)\mathrm{LR}(g))$ is the optimal theorem of that shape.

The new bound $\mathrm{noisyR}(f)=\Omega(\mathrm{R}(f)/\log(n+1))$ [PednekarPodder26STOC] combines with the outer theorem to settle composition with an input-size logarithmic loss. It applies to partial Boolean functions. The logarithm is of outer input length $n$, with no promised replacement by $\log\mathrm{R}(f)$. Constant-factor composition is false even for total functions [Meiburg26composition].

The inner hierarchy

$$\mathrm{RS}\lesssim\bar\chi\lesssim\mathrm{LR}\lesssim\mathrm{R}, \qquad\chi\le\bar\chi,\qquad\mathrm{LR}=\Omega(\sqrt{\mathrm{R}}).$$ Every adjacent pair in the first chain is separated on total functions [Meiburg26composition]. The parity-pointer family separates $\bar\chi$ from $\mathrm{RS}$ by $\Omega(\log N)$; the masked family separates $\mathrm{LR}$ from $\bar\chi$ by $\Omega(\sqrt{\log N})$; the majority family separates $\mathrm{R}$ from $\mathrm{LR}$ by $\Omega(\log N)$. Conflict and sabotage are incomparable: \(P_q\) has $\chi/\mathrm{RS}=\Omega(\log N)$, while \(\mathrm{AND}_n \circ \mathrm{OR}_n\) has $\mathrm{RS}/\chi=\Omega(\sqrt{\log N})$. The same paper gives total functions with $\mathrm{R}/\mathrm{noisyR}$ unbounded and \(H_q\) with $\mathrm{R}^{*}/\mathrm{R}=\Theta(\log\mathrm{R})$.

The total–total randomized composition example saves $\Theta(\log\mathrm{R}(g))=\Theta(\log\log L)$ in composed input length $L$. It coexists with the new $\log(n+1)$ lower bound; the scales of the two logarithms are different. The easiest case of composition is an identity outer function, i.e. solving many copies — see Direct sum and direct product.