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:
- 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.
- 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.