Write $f^{\otimes k}$ for the problem of solving $k$ independent instances of $f$ and reporting all $k$ answers. Two questions, easily confused:
- Direct sum: is $\mathrm{M}(f^{\otimes k}) \approx k\,\mathrm{M}(f)$?
- Direct product (DPT): with a budget well below $k\,\mathrm{M}(f)$, does the probability of getting all $k$ right decay like $2^{-\Omega(k)}$?
A direct product theorem is much stronger, and it is where the subtleties live. The intermediate statements have names too: a threshold DPT bounds the chance of getting $\eta k$ of them right, and an XOR lemma bounds the advantage in computing $\bigoplus_i f(x^i)$.
Scoreboard
| measure | direct sum | direct product | reference |
|---|---|---|---|
| $\mathrm{D}$ | exactly $k\,\mathrm{D}(f)$, for relations | -- | [JainKlauckSantha10, Montanaro14] |
| $\mathrm{C}$ | additive, easy | -- | folklore |
| $\mathrm{R}$ | $\Theta(k\,\mathrm{R}(f))$ up to a $\log k$ that is sometimes needed | yes, at budget $\gamma^3\mathrm{R}(f)k/11$ | [JainKlauckSantha10, BlaisBrody19, Drucker12] |
| $\bar{\mathrm{R}}$ | exactly $\Theta(k\,\bar{\mathrm{R}}_{\varepsilon/k}(f))$ | -- | [BlaisBrody19] |
| $\mathrm{Q}$ | $\tilde\Theta(k\,\mathrm{Q}(f))$, Boolean only | yes, at budget $\Omega(\mathrm{Q}(f)k)$ | [ACGT09, Reichardt11, LeeRoland13] |
Shaltiel's examples
Everything here has to dodge one construction [Shaltiel04]. Take a distribution that is hard with probability $1-\varepsilon$ and trivial with probability $\varepsilon$. One instance is hard on average; but among $k$ instances the algorithm can go hunting for the easy ones, and it finds about $\varepsilon k$ of them cheaply. So the success probability does not collapse until the budget drops below $\Theta(\varepsilon T k)$ -- a factor $\varepsilon$ below the naive $Tk$. [Drucker12] shows this is the only obstruction: his bounds match it, and they are stated with exactly that $\alpha\varepsilon Tk$ budget.
The same examples are why direct sum theorems are stated distribution-free. Relative to a fixed distribution the tight statements are false, and this is the shared root of three things in this zoo: the $\delta^2$ loss in the randomized direct sum dirsum-R, the difficulty of the randomized composition conjecture comp-R, and the invention of the \(\mathrm{Corr}_{\varepsilon}(f)\) and \(\mathrm{Sel}_{\varepsilon}(f)\) measures, whose whole content is that maximising over the distribution removes the loophole.
Why the $\log k$ is real
Solving $k$ copies by amplifying to error $1/3k$ each costs $O(k\,\mathrm{R}(f)\log k)$, and [BlaisBrody19] exhibit a total $f$ where that is optimal. The clean statement is a strong direct sum in the expected-cost measure, $\bar{\mathrm{R}}_\varepsilon(f^{k}) = \Theta(k\,\bar{\mathrm{R}}_{\varepsilon/k}(f))$ param-R-directsum, which makes visible that the direct sum question for $\mathrm{R}$ is a question about $\varepsilon$-dependence in disguise. Compare comp-R, where the same $\log$ appears in the composition upper bound for the same reason.
Relation to composition
Direct sum is composition with the outer function being the identity, so it is the easiest case -- and it is still not trivial for $\mathrm{R}$, and still open for $\mathrm{Q}$ without a log. That is a fair summary of how hard composition is.