# A strong direct sum theorem for distributional query complexity

Guy Blanc Caleb Koch Carmen Strassle Li-Yang Tan
Stanford University

###### Abstract

Consider the expected query complexity of computing the $k$-fold direct
product $f^{\otimes k}$ of a function $f$ to error $\varepsilon$ with respect
to a distribution $\mu^{k}$. One strategy is to sequentially compute each of
the $k$ copies to error $\varepsilon/k$ with respect to $\mu$ and apply the
union bound. We prove a strong direct sum theorem showing that this naive
strategy is essentially optimal. In particular, computing a direct product
necessitates a blowup in both query complexity and error.

Strong direct sum theorems contrast with results that only show a blowup in
query complexity or error but not both. There has been a long line of such
results for distributional query complexity, dating back to (Impagliazzo, Raz,
Wigderson 1994) and (Nisan, Rudich, Saks 1994), but a strong direct sum
theorem had been elusive.

A key idea in our work is the first use of the Hardcore Theorem (Impagliazzo
1995) in the context of query complexity. We prove a new “resilience lemma”
that accompanies it, showing that the hardcore of $f^{\otimes k}$ is likely to
remain dense under arbitrary partitions of the input space.

###### Contents

  1. 1 Introduction
    1. 1.1 This work
  2. 2 Broader context: Comparison with the randomized setting
    1. 2.1 A simple and near-optimal strong direct sum theorem for $\overline{\mathrm{R}}$
    2. 2.2 Error reduction fails in the distributional setting
    3. 2.3 A brief summary of our approach
  3. 3 Prior Work
    1. 3.1 Standard direct sum and product theorems
    2. 3.2 Progress and barriers towards a strong direct sum theorem
    3. 3.3 Results in light of Shaltiel’s counterexample
    4. 3.4 Summary
  4. 4 Formal statements of our results and their tightness
    1. 4.1 Tightness
  5. 5 Technical Overview for Theorem 2
    1. 5.1 Hardcore measures and the Hardcore Theorem
    2. 5.2 Two key quantities: hardcore density and hardcore advantage at a leaf
    3. 5.3 Expected total hardcore density and advantage
    4. 5.4 A resilience lemma for hardcore measures
  6. 6 Discussion and Future Work
  7. 7 Preliminaries
    1. 7.1 Randomized vs. deterministic decision trees
  8. 8 Proof of Theorem 2
    1. 8.1 The structure of this section
    2. 8.2 How hardcore density and advantage distribute over the leaves
    3. 8.3 Understanding the error in terms of hardcore density and advantage
    4. 8.4 Completing the proof of the threshold direct sum theorem
  9. 9 Equivalence between direct sum theorems and XOR lemmas and the proof of Theorem 3
    1. 9.1 Proofs of 9.1 and Theorem 3 assuming Lemma 9.3
    2. 9.2 Proof of Lemma 9.3
  10. 10 Proof of 4.1
  11. A Figures of stacked and fair trees
  12. B Proof of Theorem 4
  13. C The lack of error reduction for distributional error

##  1 Introduction

The direct sum problem seeks to understand the ways in which the complexity of
solving $k$ independent instances of a computational task scales with $k$.
This problem and its variants such as the XOR problem, where one only seeks to
compute the XOR of the $k$ output values, have a long history in complexity
theory. Research on them dates back to Strassen [Str73] and they have since
been studied in all major computational models including boolean circuits
[Yao82, Lev85, GNW11, Imp95, IW97, O’D02, IJKW08, Dru13], communication
protocols [IRW94, Sha04, KŠdW07, LSŠ08, VW08, Kla10, She11, Jai15, JPY12,
BBCR10, BRWY13, Yu22], as well as classical [IRW94, NRS94, Sha04, KŠdW07,
Dru12, BDK18, BB19, BKLS23, Hoz23] and quantum query complexity [AŠdW06,
KŠdW07, Špa08, She11, AMRR11, LR13].

###  1.1 This work

We focus on classical query complexity, and specifically distributional query
complexity. Distributional complexity, also known as average-case complexity,
is a basic notion applicable to all models of computation. Direct sum theorems
and XOR lemmas for distributional complexity, in addition to being statements
of independent interest, have found applications in areas ranging from
derandomization [Yao82, NW94, IW97] to streaming [AN21] and property testing
[BKST23].

Let $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ be a boolean function, $\mu$ be a
distribution over $\\{\pm 1\\}^{n}$, and consider the task of computing the
$k$-fold direct product $f^{\otimes
k}(X^{(1)},\ldots,X^{(k)})\coloneqq(f(X^{(1)}),\ldots,f(X^{(k)}))$ of $f$ to
error $\varepsilon$ with respect to $\mu^{k}$. One strategy is to sequentially
compute each $f(X^{(i)})$ to error $\varepsilon/k$ with respect to $\mu$ and
apply the union bound. Writing
$\overline{\mathrm{Depth}}^{\mu}(f,\varepsilon)$ to denote the minimum
expected depth of any decision tree that computes $f$ to error $\varepsilon$
w.r.t. $\mu$, this shows that:

$\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\otimes k},\varepsilon)\leq
k\cdot\overline{\mathrm{Depth}}^{\mu}(f,\tfrac{\varepsilon}{k}).$

Our main result is that this naive strategy is essentially optimal for all
functions and distributions:

######  Theorem 1 (Strong direct sum theorem for distributional query
complexity; special case of Theorem 2).

For every function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, distribution $\mu$ over
$\\{\pm 1\\}^{n}$, integer $k\in\mathds{N}$, and $\varepsilon<1$,
$\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\otimes
k},\varepsilon)\geq\tilde{\Omega}(\varepsilon^{2}k)\cdot\overline{\mathrm{Depth}}^{\mu}(f,\Theta(\tfrac{\varepsilon}{k})).$

Such direct sum theorems are termed strong, referring to the fact that they
show that computing a direct product necessitates a blowup in both the
computational resources of interest—in our case, query complexity—and error.
Strong direct sum theorems contrast with standard ones, which only show a
blowup in computational resource, and also with direct product theorems, which
focus on the blowup in error. We give a detailed overview of prior work in
Section 3, mentioning for now that while standard direct sum and direct
product theorems for distributional query complexity have long been known, a
strong direct sum theorem had been elusive. Prior to our work, it was even
open whether $\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\otimes
k},1.01\varepsilon)\geq
1.01\cdot\overline{\mathrm{Depth}}^{\mu}(f,\varepsilon)$ holds. Indeed, the
problem is known to be quite subtle, as a striking counterexample of Shaltiel
[Sha04] shows that a strong direct sum theorem is badly false if one considers
worst-case instead of expected query complexity.

##### A strong XOR lemma.

We also obtain a strong XOR lemma (Theorem 3) as a corollary of a simple
equivalence between direct sum theorems and XOR lemmas for query complexity.
One direction is immediate, since the $k$-fold XOR $f^{\oplus
k}(X^{(1)},\ldots,X^{(k)})\coloneqq f(X^{(1)})\oplus\cdots\oplus f(X^{(k)})$
can only be easier to compute than the $k$-fold direct product. For the query
model we show that the converse also holds: a direct sum theorem implies an
XOR lemma with analogous parameters.

##  2 Broader context: Comparison with the randomized setting

Direct sum theorems are also well-studied in the setting of randomized query
complexity. Recall that the $\varepsilon$-error randomized query complexity of
$f$, denoted $\overline{\mathrm{R}}(f,\varepsilon)$, is the minimum expected
depth of any randomized decision tree that computes $f$ with error at most
$\varepsilon$ for all inputs. By Yao’s minimax principle, direct sum theorems
for distributional query complexity imply analogous ones for randomized query
complexity. However, as we now elaborate, such theorems are substantially more
difficult to prove in the distributional setting.

###  2.1 A simple and near-optimal strong direct sum theorem for
$\overline{\mathrm{R}}$

For randomized query complexity, proving a strong direct sum theorem with
near-optimal parameters requires only two observations.

##### Observation #1.

The first is that a standard direct sum theorem, one without error
amplification, easily holds in the distributional setting, and hence the
randomized setting as well by Yao’s principle:

$\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\otimes
k},\varepsilon)\geq\Omega(k)\cdot\overline{\mathrm{Depth}}^{\mu}(f,\varepsilon)\quad\text{and
therefore}\quad\overline{\mathrm{R}}(f^{\otimes
k},\varepsilon)\geq\Omega(k)\cdot\overline{\mathrm{R}}(f,\varepsilon).$ (1)

The idea is that given a decision tree $T$ of average depth $q$ that computes
$f^{\otimes k}$ with error $\varepsilon$, one can extract a decision tree of
average depth $q/k$ that computes $f$ to error $\varepsilon$: place the input
in a random block $\bm{i}\sim[k]$, fill the remaining blocks with independent
random draws from $\mu$, and return the $\bm{i}$th bit of $T$’s output. It is
straightforward to show that this reduces the average depth of $T$ by a factor
of $k$ while preserving its error.

##### Observation #2.

The second observation is standard error reduction of randomized algorithms by
repetition, which in particular implies:

$\overline{\mathrm{R}}(f,\textstyle\frac{\varepsilon}{k})\leq O\left(\log
k\right)\cdot\overline{\mathrm{R}}(f,\varepsilon).$ (2)

Combining Equations 1 and 2 yields a strong direct sum theorem

$\overline{\mathrm{R}}(f^{\otimes k},\varepsilon)\geq\Omega\left(\frac{k}{\log
k}\right)\cdot\overline{\mathrm{R}}(f,\tfrac{\varepsilon}{k})$

that is within a $O(\log k)$ factor of optimal.

##### Blais–Brody.

Using more sophisticated techniques, Blais and Brody [BB19] were recently able
remove to this $O(\log k)$ factor and obtain an optimal strong direct sum
theorem for $\overline{\mathrm{R}}$. Building on their work, Brody, Kim,
Lerdputtipongporn, and Srinivasulu [BKLS23] then obtained an optimal strong
XOR lemma for $\overline{\mathrm{R}}$.

###  2.2 Error reduction fails in the distributional setting

While the crux of [BB19] and [BKLS23]’s works is the removal of a $O(\log k)$
factor, the situation is very different in the distributional setting. As
mentioned, prior to our work even a direct sum theorem where both factor-
of-$\tilde{\Omega}(k)$ blowups in Theorem 1 are replaced by 1.01 was not known
to hold.

With regards to the argument above, it is Observation #2 that breaks in the
distributional setting—not only does error reduction by repetition break, the
distributional analogue of Equation 2 is simply false. This points to a
fundamental difference between distributional and randomized complexity: while
generic error reduction of randomized algorithms is possible in all reasonable
models of computation, the analogous statement for distributional complexity
is badly false in all reasonable models of computation. For the query model
specifically, in Appendix C we give an easy proof of the following:

######  Fact 2.1.

For any $n\in\mathds{N}$ and $\mu$ being the uniform distribution over $\\{\pm
1\\}^{n}$, there is a function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ such that
$\overline{\mathrm{Depth}}^{\mu}(f,\tfrac{1}{4})=0$ and yet
$\overline{\mathrm{Depth}}^{\mu}(f,\tfrac{1}{8})\geq\Omega(n).$

###  2.3 A brief summary of our approach

We revisit Observation #1 and show how the very same extraction strategy can
in fact yield a tree with error $\Theta(\varepsilon/k)$, instead of
$\varepsilon$, at the expense of only a slight increase in depth. A key
technical ingredient in our analysis is Impagliazzo’s Hardcore Theorem
[Imp95]. For intuition as to why this theorem may be relevant for us, we note
that it is tightly connected to the notion of boosting from learning
theory—they are, in some sense, dual to each other [KS03]. And boosting is, of
course, a form of error reduction, albeit one that is more intricate than
error reduction by repetition.

See Section 5 for a detailed overview of our approach, including a discussion
of why Impagliazzo’s Hardcore Theorem, as is, does not suffice, thereby
necessitating our new “resilience lemma” that accompanies it.

##  3 Prior Work

We now place Theorem 1 within the context of prior work on direct sum and
product theorems for distributional query complexity. This is a fairly large
body of work that dates back to the 1990s.

###  3.1 Standard direct sum and product theorems

##### Standard direct sum theorems.

As we sketched in Section 2.1, a simple argument shows that

$\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\otimes
k},\varepsilon)\geq\Omega(k)\cdot\overline{\mathrm{Depth}}^{\mu}(f,\varepsilon).$
(3)

This along with an application of Markov’s inequality yields:

$\mathrm{Depth}^{\mu^{k}}(f^{\otimes
k},\varepsilon-\varepsilon^{\prime})\geq\Omega(\varepsilon^{\prime}k)\cdot\mathrm{Depth}^{\mu}(f,\varepsilon),$
(4)

where $\mathrm{Depth}^{\mu}(\cdot,\cdot)$ is the analogue of
$\overline{\mathrm{Depth}}^{\mu}(\cdot,\cdot)$ for worst-case instead of
expected query complexity. (The details of these arguments are spelt out in
[JKS10, BDK18].)

Note that the error budget is the same on both sides of Equation 3 and the
error budget on the RHS of Equation 4 is larger than that of the LHS. In a
strong direct sum theorem one seeks a lower bound even when the error budget
on the RHS is much smaller than that of the LHS, ideally by a multiplicative
factor of $k$ to match the naive upper bound.

##### A direct product theorem.

Impagliazzo, Raz, and Wigderson [IRW94] proved a direct product theorem which
focuses on the blowup in error. They showed that:

$\mathrm{Depth}^{\mu^{k}}(f^{\otimes
k},\varepsilon)\geq\mathrm{Depth}^{\mu}(f,\tfrac{\varepsilon}{k}).$ (5)

While this result has the sought-for factor of $k$ difference between the
error budgets on the LHS and RHS, it comes at the price of there no longer
being any blowup in depth.

###  3.2 Progress and barriers towards a strong direct sum theorem

These results naturally point to the problem of proving a unifying strong
direct sum theorem. We now survey efforts at such a best-of-both-worlds result
over the years.

##### Decision forests.

Nisan, Rudich, and Saks [NRS94] proved the following strengthening of
[IRW94]’s result. While [IRW94] gives an upper bound on the success
probability of a single depth-$d$ decision tree for $f^{\otimes k}$, [NRS94]
showed that the same bound holds even for decision forests where one gets to
construct a different depth-$d$ tree for each of the $k$ copies of $f$.

Since one can always stack the $k$ many depth-$d$ trees in a decision forest
to obtain a single tree of depth $kd$, [NRS94]’s result establishes a special
case of a strong direct sum theorem under a structural assumption on the tree
for $f^{\otimes k}$. See Figure 3 in Appendix A for an illustration of the
stacked decision tree that one gets from a decision forest.

##### Fair decision trees.

Building on the techniques of [NRS94], Shaltiel [Sha04] proved a strong direct
sum theorem under a different structural assumption on the tree for
$f^{\otimes k}$. He considered decision trees of depth $kd$ that are “fair” in
the sense that every path queries each of the $k$ blocks of variables at most
$d$ times. ([Sha04] actually proved a strong XOR lemma for fair decision
trees, which implies a strong direct sum theorem for such trees.) See Figure 4
in Appendix A for an illustration of a fair decision tree.

##### Shaltiel’s counterexample for worst-case query complexity.

These results of [NRS94] and [Sha04] could be viewed as evidence in favor of a
general strong direct sum theorem, one that does not impose any structural
assumptions on the tree for $f^{\otimes k}$. However, in the same paper
Shaltiel also presented an illuminating example: he constructed a function,
which we call $\mathsf{Shal}$, and a distribution $\mu$ such that for all
$k\in\mathds{N}$,

$\mathrm{Depth}^{\mu^{k}}(\mathsf{Shal}^{\otimes k},\varepsilon)\leq
O\big{(}\mathrm{Depth}^{\mu}(\mathsf{Shal},\tfrac{\varepsilon}{k})\big{)}.$
(6)

This shows, surprisingly, that for worst-case query complexity, the factor-
of-$\Omega(k)$ blowup in query complexity that one seeks in a strong direct
sum theorem is not always necessary, and in fact sometimes even a constant
factor suffices.

##### Shaltiel’s counterexample vs. Theorem 1.

This counterexample for worst-case query complexity should be contrasted with
our main result, Theorem 1, which shows that a strong direct sum theorem holds
for expected query complexity. Indeed, the starting point of our work was the
encouraging observation that Shaltiel’s function does in fact satisfy a strong
direct sum theorem if one instead considers expected query complexity. That
is, for any $\varepsilon<1$ and sufficiently large $k$,

$\overline{\mathrm{Depth}}^{\mu^{k}}(\mathsf{Shal}^{\otimes
k},\varepsilon)\geq\Omega(k)\cdot\overline{\mathrm{Depth}}^{\mu}(\mathsf{Shal},\tfrac{\varepsilon}{k}).$

This is a simple observation but appears to have been overlooked. As we now
overview, subsequent work considered other ways of sidestepping Shaltiel’s
counterexample.

###  3.3 Results in light of Shaltiel’s counterexample

##### A strong direct sum theorem for the OR function.

Klauck, Špalek, and de Wolf [KŠdW07] sidestepped Shaltiel’s counterexample by
considering a specific function (and distribution): motivated by applications
to time-space tradeoffs, they proved a strong direct sum theorem for the OR
function and with $\mu$ being its canonical hard distribution. Using this,
they also showed, for all functions $f$ a lower bound on $f^{\otimes k}$’s
query complexity in terms of $f$’s block sensitivity. This stands in contrast
to a strong direct sum theorem where one seeks a lower bound on $f^{\otimes
k}$’s query complexity in terms of $f$’s query complexity.

##### A phase transition in Shaltiel’s counterexample.

The precise parameters of Shaltiel’s counterexample are:

$\mathrm{Depth}^{\mu^{k}}(\mathsf{Shal}^{\otimes k},e^{-\Theta(\delta k)})\leq
C\delta k\cdot\mathrm{Depth}^{\mu}(\mathsf{Shal},\delta)$

for all sufficiently large constants $C$. Importantly, the multiplicative
factor on the RHS is only $\delta k$ instead of $k$, and therefore becomes a
constant if the initial hardness parameter is $\delta=\varepsilon/k$ (thereby
yielding Equation 6).

Drucker [Dru12] showed that there is a “phase transition” in Shaltiel’s
counterexample in the following sense: for all functions $f$ and a
sufficiently small constant $c>0$,

$\mathrm{Depth}^{\mu^{k}}(f^{\otimes k},1-e^{-\Theta(\delta k)})\geq c\delta
k\cdot\mathrm{Depth}^{\mu}(f,\delta).$ (7)

Therefore, while [Sha04] showed the existence of a function $\mathsf{Shal}$
such that its $k$-fold direct product can be computed to surprisingly low
error if the depth budget is $C\delta k\cdot\mathrm{Depth}^{\mu}(f,\delta)$
for a sufficiently large constant $C$, [Dru12] showed that for all functions
$f$, this stops being the case if the depth budget is instead $c\delta
k\cdot\mathrm{Depth}^{\mu}(f,\delta)$ for a sufficiently small constant $c$.

##### Query complexity with aborts.

Blais and Brody [BB19] showed that Shaltiel’s counterexample can be
sidestepped in a different way. En route to proving their strong direct sum
theorem for randomized query complexity (discussed in Section 2), they
considered decision trees $T:\\{\pm 1\\}^{n}\to\\{\pm 1,\bot\\}$ that are
allowed to output $\bot$ (“abort”) on certain inputs, and where the error of
$T$ in computing a function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ is measured with
respect to $T^{-1}(\\{\pm 1\\})$. In other words, $T$’s output on $x$ is
considered correct if $T(x)=\bot$.

Writing
$\mathrm{Depth}^{\mu}_{\operatorname{{Pr}}[\bot]\leq\frac{1}{3}}(f,\varepsilon)$
to denote the minimum depth of any decision tree for $f$ that aborts with
probability at most $1/3$ and otherwise errs with probability at most
$\varepsilon$ (both w.r.t. $\mu$), [BB19] proved that

$\mathrm{Depth}^{\mu^{k}}_{\operatorname{{Pr}}[\bot]\leq\frac{1}{3}}(f^{\otimes
k},\varepsilon)\geq\Omega(k)\cdot\mathrm{Depth}^{\mu}_{\operatorname{{Pr}}[\bot]\leq\frac{1}{3}}(f,\tfrac{\varepsilon}{k}).$
(8)

Even though the error budget on non-aborts is only $\varepsilon/k$ on the RHS,
the fact that the tree is allowed to abort with probability $1/3$ means that
it is deemed correct on a $1/3$ fraction of inputs “for free”. A decision tree
that aborts with probability $1/3$ and otherwise errs with probability
$\varepsilon/k$ can therefore be much smaller than one that never aborts and
errs with probability $\varepsilon/k$, and indeed, it is easy to construct
examples witnessing the maximally large separation:

$n=\mathrm{Depth}^{\mu}(f,\tfrac{\varepsilon}{k})\gg\mathrm{Depth}^{\mu}_{\operatorname{{Pr}}[\bot]\leq\frac{1}{3}}(f,\tfrac{\varepsilon}{k})=1.$

Building on [BB19], Brody, Kim, Lerdputtipongporn, and Srinivasulu [BKLS23]
proved a strong XOR lemma for this model of query complexity with aborts,
achieving analogous parameters.

##### A strong XOR lemma assuming hardness against all depths.

A standard strong XOR lemma states that if $f$ is hard against decision trees
of certain fixed depth $d$, then $f^{\otimes k}$ is much harder against
decision trees of depth $\Omega(dk)$. Recent work of Hoza [Hoz23] shows that
Shaltiel’s counterexample can be sidestepped if one allows for the stronger
assumption that $f$’s hardness “scales nicely” with $d$. (See the paper for
the precise statement of the resulting strong XOR lemma.)

###  3.4 Summary

Summarizing, prior work on direct sum and product theorems for distributional
query complexity either: focused on the blowup in error [IRW94] or query
complexity [JKS10, BDK18] but not both; considered restrictions (fair decision
trees [Sha04]) or variants (decision forests [NRS94]; allowing for aborts
[BB19, BKLS23]) of the query model; focused on specific functions (the OR
function [KŠdW07]); or imposed additional hardness assumptions about the
function [Hoz23]. Theorem 1, on the other hand, gives a strong direct sum
theorem that holds for all functions in the standard query model. See Table 1.

Reference |  | Error
---
Amplification
| Query
---
Amplification
| Query model/
---
Assumption
[JKS10, BDK18] | $\times$ | $\checkmark$ | Standard query model
[IRW94] | $\checkmark$ | $\times$ | Standard query model
[NRS94] | $\checkmark$ | $\checkmark$ | Decision forests
[Sha04] | $\checkmark$ | $\checkmark$ |  Fair decision trees
[KŠdW07] | $\checkmark$ | $\checkmark$ | $f=\mathrm{OR}$
[BB19, BKLS23] | $\checkmark$ | $\checkmark$ |  Decision trees with aborts
[Hoz23] | $\checkmark$ | $\checkmark$ |  Hardness against all depths
Theorem 1 | $\checkmark$ | $\checkmark$ | Standard query model
Table 1: Direct sum and product theorems for distributional query complexity

##  4 Formal statements of our results and their tightness

Theorem 1 is a special case of the following result:

######  Theorem 2 (Strong direct sum theorem).

For every function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, distribution $\mu$ over
$\\{\pm 1\\}^{n}$, $k\in\mathbb{N}$, and $\gamma,\delta\in(0,1)$, we have that

$\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\otimes k},1-e^{-\Theta(\delta
k)}-\gamma)\geq\Omega\left(\frac{\gamma^{2}k}{\log(1/\delta)}\right)\cdot\overline{\mathrm{Depth}}^{\mu}(f,\delta).$

We in fact prove a strong threshold direct sum theorem which further
generalizes Theorem 2: while a direct sum theorem shows that $f^{\otimes k}$
is hard to compute, i.e. it is hard to get all $k$ copies of $f$ correct, a
threshold direct sum theorem shows that it is hard even to get most of the $k$
copies of $f$ correct. See Theorem 5.

By the equivalence between strong direct sum theorems and strong XOR lemmas
(9.1), we also get:

######  Theorem 3 (Strong XOR lemma).

For every function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ and distribution $\mu$
over $\\{\pm 1\\}^{n}$, $k\in\mathds{N}$, and $\gamma,\delta\in(0,1)$, we have
that

$\overline{\mathrm{Depth}}^{\mu^{k}}\left(f^{\oplus
k},\tfrac{1}{2}(1-e^{-\Theta(\delta
k)}-\gamma)\right)\geq{\Omega}\left(\frac{\gamma^{2}k}{\log(1/\delta)}\right)\cdot\overline{\mathrm{Depth}}^{\mu}(f,\delta).$

###  4.1 Tightness

Theorem 2 amplifies an initial hardness parameter of $\delta=\Theta(1/k)$ to
$1-\gamma$ for any small constant $\gamma$ with a near-optimal overhead of

$\Omega\left(\frac{\gamma^{2}k}{\log(1/\delta)}\right)=\Omega\left(\frac{k}{\log
k}\right).$

However, due to the polynomial dependence on $\gamma$, we cannot achieve a
final hardness parameter that is exponentially close to $1$ as a function of
$k$. We show that this is unavoidable since at least a linear dependence on
$\gamma$ is necessary:

######  Claim 4.1 (Linear dependence on $\gamma$ is necessary).

Let $\mathsf{Par}:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ be the parity function and
$\mu$ be the uniform distribution over $\\{\pm 1\\}^{n}$. Then for all
$\gamma$,

$\overline{\mathrm{Depth}}^{\mu^{k}}(\mathsf{Par}^{\otimes k},1-\gamma)\leq
O(\gamma k)\cdot\overline{\mathrm{Depth}}^{\mu}(\mathsf{Par},\tfrac{1}{4}).$

The same example shows that a linear dependence on $\gamma$ is likewise
necessary in the setting of XOR lemmas. Determining the optimal polynomial
dependence on $\gamma$ in both settings, as well as the necessity of the
$\log(1/\delta)$ factor, are concrete avenues for future work.

##  5 Technical Overview for Theorem 2

###  5.1 Hardcore measures and the Hardcore Theorem

At the heart of our proof is the notion of a hardcore measure and
Impagliazzo’s Hardcore Theorem [Imp95], both adapted to the setting of query
complexity.

######  Definition 5.1 (Hardcore measure for query complexity).

We say that $H:\\{\pm 1\\}^{n}\to[0,1]$ is a $(\gamma,d)$-hardcore measure for
$f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ w.r.t. $\mu$ of density $\delta$ if:

  1. 1.

$H$’s density is $\delta$:
$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mu}[H(\bm{x})]=\delta$.

  2. 2.

$d$-query algorithms achieve correlation at most $\gamma$ with $f$ on $H$:

$\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mu}[f(\bm{x})T(\bm{x})H(\bm{x})]\leq\gamma\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mu}[H(\bm{x})]=\gamma\delta.$

for all decision trees $T$ whose expected depth w.r.t. $\mu$ is at most $d$.

######  Theorem 4 (Hardcore Theorem for query complexity).

For every function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, distribution $\mu$ over
$\\{\pm 1\\}^{n}$, and $\gamma,\delta>0$, there exists a $(\gamma,d)$-hardcore
measure $H$ for $f$ of density $\delta/2$ w.r.t. $\mu$ where

$d=\Theta\left(\frac{\gamma^{2}}{\log(1/\delta)}\right)\overline{\mathrm{Depth}}^{\mu}(f,\delta).$

The Hardcore Theorem was originally proved, and remains most commonly used, in
the setting of circuit complexity where it has long been recognized as a
powerful result. (See e.g. [Tre07], where it is described as “one of the bits
of magic of complexity theory”.) We show in Appendix B that its proof extends
readily to the setting of query complexity to establish Theorem 4. Despite its
importance in circuit complexity and its straightforward extension to query
complexity, our work appears to be the first to consider its applicability in
the latter setting.

######  Remark 5.2.

For intuition regarding Definition 5.1, note that if $H:\\{\pm
1\\}^{n}\to\\{0,1\\}$ is the indicator of a set, the two properties simplify
to: $\displaystyle\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mu}[\bm{x}\in
H]=\delta$ and
$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mu}[f(\bm{x})T(\bm{x})\mid\bm{x}\in
H]\leq\gamma$.

###  5.2 Two key quantities: hardcore density and hardcore advantage at a leaf

##### Setup.

For the remainder of this section, we fix a function $f:\\{\pm
1\\}^{n}\to\\{\pm 1\\}$, distribution $\mu$ over $\\{\pm 1\\}^{n}$, and
initial hardness parameter $\delta$ (which we think of as small, close to
$0$). Let $T:(\\{\pm 1\\}^{n})^{k}\to\\{\pm 1\\}^{k}$ be a decision tree that
seeks to compute $f^{\otimes k}$ w.r.t. $\mu^{k}$. Our goal is to show that
$T$’s error must be large, close to $1$, unless its depth is sufficient large.

##### Definitions of the hardcore density and hardcore advantage at a leaf.

Let $H:\\{\pm 1\\}^{n}\to[0,1]$ be a $(\gamma,d)$-hardcore measure for $f$ of
density $\delta$ w.r.t. $\mu$ given by Theorem 4. Each leaf $\ell$ of $T$
corresponds to a tuple of restrictions $(\pi_{1},\ldots,\pi_{k})$ to each of
the $k$ blocks of inputs. We will be interested in understanding, for a random
block $\bm{i}\in[k]$, the extent to which the restricted function
$H_{\pi_{\bm{i}}}$ retains the two defining properties of a hardcore measure:
high density and strong hardness. We therefore define:

######  Definition 5.3 (Hardcore density at $\ell$).

For $i\in[k]$, the hardcore density at $\ell$ in the $i$th block is the
quantity:

$\mathrm{Dens}_{H}(\ell,i)\coloneqq\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}\big{[}H(\bm{X}^{(i)})\mid\text{$\bm{X}$
reaches $\ell$}\big{]}.$

The total hardcore density at $\ell$ is the quantity
$\displaystyle\mathrm{Dens}_{H}(\ell)\coloneqq\sum_{i=1}^{k}\mathrm{Dens}_{H}(\ell,i).$

See Figure 1 for an illustration of Definition 5.3.

$\pi$$H$$H$$H$,,,,Leaf $\ell$Hardcore measure $H_{\pi_{1}}$ with
$\mathrm{Dens}_{H}(\ell,1)={\mathrm{area}(\leavevmode\hbox to7.23pt{\vbox
to7.23pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
{}{}{}{{}}{}{{}{}{}{{}}{{{}{}{}{}}}}{} {} {} {}
{}{}\pgfsys@beginscope\pgfsys@invoke{
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@invoke{
}\pgfsys@color@gray@fill{0}\pgfsys@invoke{
}\definecolor[named]{pgffillcolor}{rgb}{0,0,0}\definecolor{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@gray@fill{0.85}\pgfsys@invoke{
}{}{}\pgfsys@moveto{6.82881pt}{0.0pt}\pgfsys@curveto{6.82881pt}{3.77148pt}{3.77148pt}{6.82881pt}{0.0pt}{6.82881pt}\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope; {}{{}}{} {}{} {}{}
{}\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgffillcolor}{rgb}{0.85,0.85,0.85}\pgfsys@color@gray@fill{0.85}\pgfsys@invoke{
}\pgfsys@stroke@opacity{0.0}\pgfsys@invoke{
}\pgfsys@fill@opacity{0.0}\pgfsys@invoke{
}\pgfsys@fill@opacity{1}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{6.82881pt}\pgfsys@lineto{6.82881pt}{0.0pt}\pgfsys@closepath\pgfsys@fillstroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{}{{}}{}
{}{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{6.82881pt}\pgfsys@stroke\pgfsys@invoke{
} {}{{}}{}
{}{}{}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{6.82881pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}})}/{\mathrm{area}(\square})$Queries
along path $\pi$ Figure 1: Illustration of a hardcore density. The tree
$T:(\\{\pm 1\\}^{n})^{3}\to\\{\pm 1\\}^{3}$ seeks to compute a function
$f^{\otimes 3}$. The tuple of squares at the top of the figure illustrates the
set of all inputs to the function while the strings in the support of the
hardcore measure are shaded gray. The tuple at the bottom of the figure
illustrates the set of inputs reaching the leaf $\ell$. Each block is the
subcube consistent with the path $\pi$ and the shaded region denotes the
fragment of $H$ which is contained in the corresponding subcube.

######  Definition 5.4 (Hardcore advantage at $\ell$).

For $i\in[k]$, the hardcore advantage at $\ell$ in the $i$th block is the
quantity:

$\mathrm{Adv}_{H}(\ell,i)\coloneqq\Big{|}\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}\big{[}f(\bm{X}^{(i)})T(\bm{X})_{i}H(\bm{X}^{(i)})\mid\text{$\bm{X}$
reaches $\ell$}\big{]}\Big{|}.$

The total hardcore advantage at $\ell$ is the quantity
$\displaystyle\mathrm{Adv}_{H}(\ell)\coloneqq\sum_{i=1}^{k}\mathrm{Adv}_{H}(\ell,i).$

Intuitively, leaves for which $\mathrm{Dens}_{H}(\ell)$ is large and
$\mathrm{Adv}_{H}(\ell)$ is small contribute significantly to error of $T$.
Lemma 5.5 below formalizes this:

##### Notation

(Canonical distribution over leaves). We write $\mu^{k}(T)$ to denote the
distribution over leaves of $T$ where:

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{\ell}\sim\mu^{k}(T)}[\bm{\ell}=\ell]=\mathop{{\operatorname{{Pr}}}\/}_{\bm{X}\sim\mu^{k}}[\text{$\bm{X}$
reaches $\ell$}].$

######  Lemma 5.5 (Accuracy in terms of hardcore density and advantage at
leaves).

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{X}\sim\mu^{k}}[T(\bm{X})=f^{\otimes
k}(\bm{X})]\leq\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\left[\exp\left(-\frac{\mathrm{Dens}_{H}(\bm{\ell})-\mathrm{Adv}_{H}(\bm{\ell})}{4}\right)\right].$

###  5.3 Expected total hardcore density and advantage

Lemma 5.5 motivates understanding the random variables
$\mathrm{Dens}_{H}(\bm{\ell})$ and $\mathrm{Adv}_{H}(\bm{\ell})$ for
$\bm{\ell}\sim\mu^{k}(T)$. We begin by bounding their expectations:

######  Claim 5.6 (Expected total hardcore density).

If $H$ is a hardcore measure of density $\delta$ then

$\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}[\mathrm{Dens}_{H}(\bm{\ell})]=\delta
k.$

5.6 is a statement about density preservation. It says that $H$’s expected
density at a random leaf $\bm{\ell}\sim\mu^{k}(T)$ and in a random block
$\bm{i}\sim[k]$ is equal to $H$’s initial density:

$\mathop{\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}}_{\bm{i}\sim[k]}\bigg{[}\underbrace{\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}\big{[}H(\bm{X}^{(\bm{i})})\mid\text{$\bm{X}$
reaches
$\bm{\ell}$}\big{]}}_{\mathrm{Dens}_{H}(\bm{\ell},\bm{i})}\bigg{]}=\delta=\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mu}[H(\bm{X})].$

######  Claim 5.7 (Expected total hardcore advantage).

If $H$ is a $(\gamma,d)$-hardcore measure for $f$ of density $\delta$ w.r.t.
$\mu$ and the expected depth of $T$ is at most $dk$, then

$\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}[\mathrm{Adv}_{H}(\bm{\ell})]\leq\gamma\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}[\mathrm{Dens}_{H}(\bm{\ell})].$

5.7 is a statement about depth amplification. By definition, $H$ being a
$(\gamma,d)$-hardcore measure for $f$ means that

$\underbrace{\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mu}[f(\bm{x})T_{\textnormal{small}}(\bm{x})H(\bm{x})]}_{\textnormal{Hardcore
advantage}}\leq\gamma\underbrace{\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mu}[H(\bm{x})]}_{\textnormal{Hardcore
density}}$

for every tree $T_{\mathrm{small}}:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ of expected
depth $d$. 5.7 says that

$\underbrace{\sum_{i=1}^{k}\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}\big{[}f(\bm{X}^{(i)})T_{\textnormal{large}}(\bm{X})_{i}H(\bm{X}^{(i)})\big{]}}_{\textnormal{Total
hardcore
advantage}}\leq\gamma\underbrace{\sum_{i=1}^{k}\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}[H(\bm{X}^{(i)})]}_{\textnormal{Total
hardcore density}}.$

for every tree $T_{\textnormal{large}}:(\\{\pm 1\\}^{n})^{k}\to\\{\pm
1\\}^{k}$ of expected depth $dk$. Crucially, the depth of
$T_{\textnormal{large}}$ is allowed to be a factor of $k$ larger than that of
$T_{\textnormal{small}}$, and yet the ratio of hardcore advantage to hardcore
density remains the same ($\gamma$ in both cases).

####  5.3.1 Done if Jensen went the other way

For intuition as to why 5.6 and 5.7 are relevant yet insufficient for us, note
that if it were the case that
$\mathbb{E}[\exp(-\bm{Z})]\leq\exp(-\mathbb{E}[\bm{Z}])$, which unfortunately
is the opposite of what Jensen’s inequality gives, we would have the strong
bound on the accuracy of $T$ that we seek:

$\displaystyle\mathop{{\operatorname{{Pr}}}\/}_{\bm{X}\sim\mu^{k}}[T(\bm{X})=f^{\otimes
k}(\bm{X})]$
$\displaystyle\leq\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\left[\exp\left(-\frac{\mathrm{Dens}_{H}(\bm{\ell})-\mathrm{Adv}_{h}(\bm{\ell})}{4}\right)\right]$
(Lemma 5.5)
$\displaystyle``\leq"\exp\bigg{(}-\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\bigg{[}\frac{\mathrm{Dens}_{H}(\bm{\ell})-\mathrm{Adv}_{H}(\bm{\ell})}{4}\bigg{]}\bigg{)}$
(Wrong direction of Jensen) $\displaystyle\leq\exp\bigg{(}-\frac{\delta
k-\gamma\delta k}{4}\bigg{)}$ (5.6 and 5.7)
$\displaystyle\leq\exp(-\Theta(\delta k)).$

For an actual proof, we need to develop a more refined understanding of the
distribution of $\mathrm{Dens}_{H}(\bm{\ell})$ beyond just its expectation.
(As it turns out, this along with the bound on
$\mathbb{E}[\mathrm{Adv}_{H}(\bm{\ell})]$ given by 5.7 suffices.)

###  5.4 A resilience lemma for hardcore measures

##### An illustrative bad case to rule out.

Suppose $T$ were such that it achieved
$\mathbb{E}[\mathrm{Dens}_{H}(\bm{\ell})]=\delta k$ by having a
$\delta$-fraction of leaves with $\mathrm{Dens}_{H}(\ell)=k$ and the remaining
$1-\delta$ fraction with $\mathrm{Dens}_{H}(\ell)=0$. If this were the case
then “all the hardness” would be concentrated on a small $\delta$ fraction of
leaves, and the best lower bound that we would be able to guarantee on error
of $T$ with respect to $f^{\otimes k}$ would only be $\delta$. This is our
starting assumption on the hardness of $f$, and so no error amplification has
occurred.

##### The resilience lemma.

We rule out cases like this by showing that $T$ must achieve
$\mathbb{E}[\mathrm{Dens}_{H}(\bm{\ell})]=\delta k$ by having the vast
majority of its leaves with $\mathrm{Dens}_{H}(\ell)=\Omega(\delta k)$, i.e.
that $\mathrm{Dens}_{H}(\bm{\ell})$ is tightly concentrated around its
expectation:

######  Lemma 5.8 (Resilience lemma).

For any hardcore measure $H$ of density $\delta$ w.r.t. $\mu$ and tree
$T:(\\{\pm 1\\}^{n})^{k}\to\\{\pm 1\\}^{k}$,
$\mathop{{\operatorname{{Pr}}}\/}_{\bm{\ell}\sim\mu^{k}(T)}[\mathrm{Dens}_{H}(\bm{\ell})\leq\delta
k/2]\leq e^{-\delta k/8}.$ Similarly,
$\displaystyle\mathop{{\operatorname{{Pr}}}\/}_{\bm{\ell}\sim\mu^{k}(T)}[\mathrm{Dens}_{H}(\bm{\ell})\geq
2\delta k]\leq e^{-\delta k/3}.$

Leaf $\ell$ with $\mathrm{Dens}_{H}(\ell)=0$
$\delta$-fraction$(1-\delta)$-fraction$~{}k\quad k\quad k\quad k\quad k\quad
0\quad 0\quad 0\quad 0\quad 0\quad 0\quad 0$ (a) An illustration of the bad
case where $\mathrm{Dens}_{H}$ is anti-concentrated away from its mean of
$\delta k$.

Leaf $\ell$ with $\mathrm{Dens}_{H}(\ell)\approx\delta k$ $\approx\delta
k~{}~{}\approx\delta k~{}~{}\approx\delta k~{}~{}\approx\delta
k~{}~{}\approx\delta k~{}~{}\approx\delta k$ (b) An illustration of the good
case where $\mathrm{Dens}_{H}$ is concentrated around its mean of $\delta k$.

Figure 2: An illustration of our resilience lemma (Lemma 5.8). This lemma
shows that all trees resemble the one on the right, with
$\mathrm{Dens}_{H}(\bm{\ell})$ tightly concentrated around its mean of $\delta
k$. This allows us to rule out bad trees such as those on the left where all
of the hardness is concentrated on a small fraction of the leaves.

Comparing Lemma 5.8 to 5.7, we see that 5.7 is a statement about density
preservation in expectation whereas Lemma 5.8 is a statement about density
preservation with high probability. It says that $H$’s density at a random
leaf $\bm{\ell}\sim\mu^{k}(T)$ and in a random block $\bm{i}\sim[k]$ remains,
with high probability, roughly the same as that of $H$’s initial density—this
is why we call Lemma 5.8 a resilience lemma. (Our proof of Lemma 5.8 in fact
shows that the $H$’s density remains resilient under arbitrary partitions of
$(\\{\pm 1\\}^{n})^{k}$, not just those induced by a decision tree.)

With Lemma 5.8 in hand, the intuition sketched in Section 5.3.1 can be made
formal.

##  6 Discussion and Future Work

Our main results are a strong direct sum theorem and a strong XOR lemma for
distributional query complexity, showing that if $f$ is somewhat hard to
approximate with depth-$d$ decision trees, then $f^{\otimes k}$ and $f^{\oplus
k}$ are both much harder to approximate, even with decision trees of much
larger depth. These results hold for expected query complexity, and they
circumvent a counterexample of Shaltiel showing that such statements are badly
false for worst-case query complexity. We view our work as confirming a remark
Shaltiel made in his paper, that his counterexample “seems to exploit defects
in the formulation of the problem rather than show that our general intuition
for direct product assertions is false.”

Shaltiel’s counterexample applies to many other models including boolean
circuits and communication protocols. A broad avenue for future work is to
understand how this counterexample can be similarly circumvented in these
models by working with more fine-grained notions of computation cost. Consider
for example boolean circuit complexity and Yao’s XOR lemma [Yao82], which
states that if $f$ is mildly hard to approximate with size-$s$ circuits w.r.t.
$\mu$, then $f^{\oplus k}$ is extremely hard to approximate with
size-$s^{\prime}$ circuits w.r.t. $\mu^{k}$. A well-known downside of this
important result is that it only holds for $s^{\prime}\ll s$. Indeed,
Shaltiel’s counterexample shows that it cannot hold for $s^{\prime}\gg s$, at
least not for the standard notion of circuit size. Extrapolating from our
work, can we prove a strong XOR lemma for boolean circuits by considering a
notion of the “expected size” of a circuit $C:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$
with respect to a distribution $\mu$ over $\\{\pm 1\\}^{n}$? A natural
approach is to consider the standard notion of the expected runtime of a
Turing machine with respect to a distribution over inputs and have the
Cook–Levin theorem guide us towards an appropriate analogue for circuit size.

On a more technical level, a crucial ingredient in our work is the first use
of Impagliazzo’s Hardcore Theorem within the context of query complexity (and
indeed, to our knowledge, the first use of it outside of circuit complexity).
Could this powerful theorem be useful for other problems in query complexity,
possibly when used in conjunction with our new resilience lemma?

##  7 Preliminaries

We use $[n]$ to denote the set $\\{1,2,\ldots,n\\}$ and bold font (e.g
$\bm{x}\sim\mathcal{D}$) to denote random variables. For any distribution
$\mu$, we use $\mu^{k}$ to denote $k$-fold the product distribution
$\mu\times\cdots\times\mu$.

For any function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, we use $f^{\otimes
k}:(\\{\pm 1\\}^{n})^{k}\to\\{\pm 1\\}^{k}$ to denote its $k$-fold direct
product,

$f^{\otimes
k}(X^{(1)},\ldots,X^{(k)})\coloneqq\big{(}f(X^{(1)}),\ldots,f(X^{(k)})\big{)}.$

Similarly, we use $f^{\oplus k}:(\\{\pm 1\\}^{n})^{k}\to\\{\pm 1\\}$ to denote
its $k$-fold direct sum,

$f^{\oplus k}(X^{(1)},\ldots,X^{(k)})\coloneqq\prod_{i\in[k]}f(X^{(i)}).$

######  Definition 7.1 (Bernoulli distribution).

For any $\delta\in[0,1]$, we write $\mathrm{Ber}(\delta)$ to denote the
distribution of $\bm{z}$ where $\bm{z}=1$ with probability $\delta$ and $0$
otherwise.

######  Definition 7.2 (Binomial distribution).

For any $k\in\mathds{N}$, $\delta\in[0,1]$, we write $\mathrm{Bin}(k,\delta)$
to denote the sum of $k$ independent random variables drawn from
$\mathrm{Ber}(\delta)$.

######  Fact 7.3 (Chernoff bound).

Let $\bm{z}_{1},\ldots,\bm{z}_{k}$ be independent and each bounded within
$[0,1]$ and $\bm{Z}\coloneqq\sum_{i\in[k]}\bm{z}_{i}$. For any threshold
$t\leq\mu\coloneqq\mathop{{\mathds{E}}\/}[\bm{Z}]$,

$\operatorname{{Pr}}[\bm{Z}\leq
t]\leq\exp\left(-\tfrac{(\mu-t)^{2}}{2\mu}\right).$

Similar bounds for the probability $\bm{Z}$ exceeds its mean hold. For
example,

$\operatorname{{Pr}}[\bm{Z}\geq 2\mu]\leq\exp\left(-\tfrac{\mu}{3}\right).$

Furthermore, the above bounds also hold for any random variable $\bm{Y}$
satisfying
$\mathop{{\mathds{E}}\/}[e^{\lambda\bm{Y}}]\leq\mathop{{\mathds{E}}\/}[e^{\lambda\bm{Z}}]$
for all $\lambda\in\mathds{R}$.

###  7.1 Randomized vs. deterministic decision trees

We will prove all of our results with respect to the expected depth of a
_randomized_ decision tree. In this subsection, we formally define
_deterministic_ and _randomized_ decision trees and prove that our results
easily extend to the deterministic setting.

######  Definition 7.4 (Deterministic decision tree).

A deterministic decision tree, $T:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, is a binary
tree with two types of nodes: Internal nodes each query some $x_{i}$ for
$i\in[n]$ and have two children whereas leaf nodes are labeled by a bit
$b\in\\{\pm 1\\}$ and have no children. On input $x\in\\{\pm 1\\}^{n}$, $T(x)$
is computed as follows: We proceed through $T$ starting at the root. Whenever
at an internal node that queries the $i^{\text{th}}$ coordinate, we proceed to
the left child if $x_{i}=-1$ and right child if $x_{i}=+1$. Once we reach a
leaf, we output the label of that leaf.

######  Definition 7.5 (Randomized decision tree).

A randomized decision tree, $\mathcal{T}:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, is
distribution over deterministic decision trees. On input $x\in\\{\pm
1\\}^{n}$, it first draws ${\bm{T}}\sim\mathcal{T}$ and then outputs
${\bm{T}}(x)$.

######  Definition 7.6 (Expected depth).

For any deterministic decision tree $T:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ and
distribution $\mu$ on $\\{\pm 1\\}^{n}$, we use
$\overline{\mathrm{Depth}}^{\mu}(T)$ to denote the expected depth of $T$,
which is the expected number of coordinates $T$ queries on a random input
$\bm{x}\sim\mu$. Similarly, for a randomized decision tree $\mathcal{T}$,
$\overline{\mathrm{Depth}}^{\mu}(\mathcal{T})\coloneqq\mathop{{\mathds{E}}\/}_{{\bm{T}}\sim\mathcal{T}}[\overline{\mathrm{Depth}}^{\mu}({\bm{T}})]$.

We write $\overline{\mathrm{Depth}}^{\mu}(\cdot,\cdot)$ to denote the minimum
expected depth of _any_ decision tree, including randomized decision trees.
Thus, all of our main results, as written, hold for _randomized_ decision
trees; however, equivalent statements are true if we restrict ourselves to
only _deterministic_ decision trees, with only a small change in constants, as
easily seen from the following claim.

######  Claim 7.7.

For any $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, distribution $\mu$, and constant
$\varepsilon$,

$\overline{\mathrm{Depth}}^{\mu}(f,2\varepsilon)\leq\overline{\mathrm{Depth}}^{\mu}_{\det}(f,2\varepsilon)\leq
2\cdot\overline{\mathrm{Depth}}^{\mu}(f,\varepsilon).$

###### Proof.

The left-most inequality follows immediately from that fact that any
deterministic decision tree is also a randomized decision tree. For the second
inequality, given any randomized decision tree $\mathcal{T}$ with error
$\varepsilon$ and expected depth $d$, we’ll construct a deterministic decision
tree $T$ with error at most $2\varepsilon$ and expected depth at most $2d$.
First, we decompose the expected error of $\mathcal{T}$:

$\varepsilon=\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mu}[\mathcal{T}(\bm{x})\neq
f(\bm{x})]=\mathop{{\mathds{E}}\/}_{{\bm{T}}\sim\mathcal{T}}\Big{[}\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mu}[{\bm{T}}(\bm{x})\neq
f(\bm{x})]\Big{]}.$

Applying Markov’s inequality, if we sample ${\bm{T}}\sim\mathcal{T}$, with
probability at least $1/2$, it has error at most $\varepsilon$. Similarly,
since the expected depth of $\mathcal{T}$ is $d$, with probability at least
$1/2$, ${\bm{T}}$ will have expected depth at most $2d$. By union bound, there
is a nonzero probability that we choose a single (deterministic) tree with
error at most $2\varepsilon$ and expected depth at most $2d$. ∎

7.7 immediately allows direct sum theorems for _randomized_ decision trees to
also apply to _deterministic_ decision trees.

######  Corollary 7.8 (Randomized direct sum theorems imply deterministic
ones).

Suppose that a randomized direct sum theorem of the following form holds. For
a function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, distribution $\mu$ over $\\{\pm
1\\}^{n}$, $k\in\mathbb{N}$, and constants $\varepsilon,\delta,M$,

$\overline{\mathrm{Depth}}^{\mu^{\otimes k}}(f^{\otimes k},\varepsilon)\geq
M\cdot\overline{\mathrm{Depth}}^{\mu}(f,\delta).$

Then,

$\overline{\mathrm{Depth}}_{\det}^{\mu^{\otimes k}}(f^{\otimes
k},\varepsilon)\geq\overline{\mathrm{Depth}}^{\mu^{\otimes k}}(f^{\otimes
k},\varepsilon)\geq
M\cdot\overline{\mathrm{Depth}}^{\mu}(f,\delta)\geq\tfrac{M}{2}\cdot\overline{\mathrm{Depth}}^{\mu}_{\mathrm{det}}(f,2\delta).$

With Corollary 7.8 in mind, the remainder of this paper will only consider
_randomized_ decision trees.

##  8 Proof of Theorem 2

The purpose of this section is to prove our direct sum theorem (Theorem 2)
showing that if $f$ is hard to compute, than $f^{\otimes k}$ is even harder to
compute. We will in fact prove a threshold direct sum theorem, showing that it
is hard even to get most of the $k$ copies correct. To formalize this, we
generalize the notation $\overline{\mathrm{Depth}}(\cdot,\cdot)$ to take in an
additional threshold parameter $t$ specifying how many blocks we allow to be
wrong.

######  Definition 8.1.

For any function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, error $\varepsilon$, and
threshold $t\in\mathds{N}$, we use
$\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\otimes},\varepsilon,t)$ to denote the
minimum expected depth of a tree $T:(\\{\pm 1\\}^{n})^{k}\to\\{\pm 1\\}^{k}$
satisfying

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{X}\sim\mu^{k}}\left[\|T(\bm{X})-f^{\otimes
k}(\bm{X})\|_{0}]>t\right]\leq\varepsilon.$

######  Theorem 5 (A strong threshold direct sum theorem for query
complexity).

For every function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, distribution $\mu$ over
$\\{\pm 1\\}^{n}$, $k\in\mathds{N}$, and $\gamma,\delta\in(0,1)$,

$\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\otimes k},1-e^{-\Omega(\delta
k)}-\gamma,\Omega(\delta
k))\geq\Omega\left(\frac{\gamma^{2}k}{\log(1/\delta)}\right)\cdot\overline{\mathrm{Depth}}^{\mu}(f,\delta).$

Note that the threshold of $\Omega(\delta k)$ is within a constant factor of
optimal, as repeating an algorithm that errs $\delta$ fraction of the time $k$
times will lead to an average of $\delta k$ mistakes. Theorem 5 implies our
standard strong direct sum theorem (Theorem 2) because

$\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\otimes
k},\varepsilon,t)\geq\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\otimes
k},\varepsilon,0)=\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\otimes
k},\varepsilon)$

for any $t\geq 0$ and $\varepsilon>0$.

###  8.1 The structure of this section

By the Hardcore Theorem (Theorem 4), proving Theorem 5 reduces to proving:

######  Theorem 6 (Hardness of $f^{\otimes k}$ in terms of a hardcore measure
for $f$).

Suppose that $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ has an $(\gamma,d)$-hardcore
measure w.r.t $\mu$ of density $\delta$. Then, for any $T:(\\{\pm
1\\}^{n})^{k}\to\\{\pm 1\\}^{k}$ with
$\overline{\mathrm{Depth}}^{\mu^{k}}(T)\leq kd$,
$\mathop{{\operatorname{{Pr}}}\/}_{\bm{X}\sim\mu^{k}}\left[\|T(\bm{X})-f^{\otimes
k}(\bm{X})\|_{0}\leq\textstyle\frac{\delta k}{10}\right]\leq e^{-\frac{\delta
k}{10}}+10\gamma.$

This section is therefore devoted to proving Theorem 6. As discussed in
Section 5, our proof tracks two key quantities: we will analyze how hardcore
density (Definition 5.3) and hardcore advantage (Definition 5.4) are
distributed over the leaves of $T$. This proof will be broken into three
steps:

  1. 1.

In Section 8.2, we prove 5.7 and Lemma 5.8, which aim to understand the
distributions of the hardcore density and hardcore advantage of a random leaf
of $T$.

  2. 2.

In Section 8.3, we derive an expression for the probability $T$ makes
surprisingly few mistakes as a function of the hardcore density and hardcore
advantage at each leaf. This generalizes Lemma 5.5.

  3. 3.

In Section 8.4, we combine the above to prove Theorem 6.

###  8.2 How hardcore density and advantage distribute over the leaves

We begin with proving our resilience lemma for hardcore density. Roughly
speaking, this will say that for any tree $T:(\\{\pm 1\\}^{n})^{k}\to\\{\pm
1\\}^{k}$, the hardcore density of a random leaf concentrates around $\delta
k$. We recall the definition of hardcore density.

######  Definition 8.2 (Hardcore density at $\ell$, Definition 5.3 restated).

For any tree $T:(\\{\pm 1\\}^{n})^{k}\to\\{\pm 1\\}^{k}$, hardcore measure
$H:\\{\pm 1\\}^{n}\to[0,1]$, distribution $\mu$ on $\\{\pm 1\\}^{n}$,
$i\in[k]$, and leaf $\ell$ of $T$, the hardcore density at $\ell$ in the $i$th
block is the quantity:

$\mathrm{Dens}_{H}(\ell,i)\coloneqq\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}\big{[}H(\bm{X}^{(i)})\mid\text{$\bm{X}$
reaches $\ell$}\big{]}.$

The total hardcore density at $\ell$ is the quantity
$\displaystyle\mathrm{Dens}_{H}(\ell)\coloneqq\sum_{i=1}^{k}\mathrm{Dens}_{H}(\ell,i).$

The distribution over leaves in the resilience lemma is the canonical
distribution.

######  Definition 8.3 (Canonical distribution).

For any tree $T$ and distribution $\mu$ over $T$’s domain, we write $\mu(T)$
to denote the distribution over leaves of $T$ where:

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{\ell}\sim\mu^{k}(T)}[\bm{\ell}=\ell]=\mathop{{\operatorname{{Pr}}}\/}_{\bm{X}\sim\mu}[\text{$\bm{X}$
reaches $\ell$}].$

######  Lemma 8.4 (Resilience lemma, generalization of Lemma 5.8).

For any $T:(\\{\pm 1\\}^{n})^{k}\to\\{\pm 1\\}^{k}$, hardcore measure $H$,
distribution $\mu$, and convex $\Phi:\mathds{R}\to\mathds{R}$,

$\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}[\Phi(\mathrm{Dens}_{H}(\bm{\ell}))]\leq\mathop{{\mathds{E}}\/}_{\bm{z}\sim\mathrm{Bin}(k,\delta)}[\Phi(\bm{z})]$

where $\delta\coloneqq\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mu}[H(\bm{x})]$ is
the density of $H$ w.r.t. $\mu$.

###### Proof.

Draw $\bm{X}\sim\mu^{k}$. Then, for each $i\in[k]$, independently draw
$\bm{z}_{i}\sim\mathrm{Ber}(H(\bm{X}^{(i)}))$. Note that, for any leaf $\ell$
and $i\in[k]$,

$\mathrm{Dens}_{H}(\ell,i)\coloneqq\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}[H(\bm{X}^{(i)})\mid\bm{X}\text{
reaches
}\bm{\ell}]=\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}[\bm{z}_{i}\mid\bm{X}\text{
reaches }\bm{\ell}].$

By the above equality and definition
$\mathrm{Dens}_{H}(\ell)=\sum_{i\in[k]}\mathrm{Dens}_{H}(\ell,i)$,

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}[\Phi(\mathrm{Dens}_{H}(\bm{\ell}))]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\Bigg{[}\Phi\Bigg{(}\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}\Bigg{[}\sum_{i\in[k]}\bm{z}_{i}\mid\bm{X}\text{
reaches }\bm{\ell}\Bigg{]}\Bigg{)}\Bigg{]}$
$\displaystyle\leq\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\Bigg{[}\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}\Bigg{[}\Phi\Bigg{(}\sum_{i\in[k]}\bm{z}_{i}\mid\bm{X}\text{
reaches }\bm{\ell}\Bigg{)}\Bigg{]}\Bigg{]}$ (Jensen’s inequality)
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}\Bigg{[}\Phi\Bigg{(}\sum_{i\in[k]}\bm{z}_{i}\Bigg{)}\Bigg{]}.$
(Law of total expectation)

Note that the last line holds precisely for the distribution $\mu^{k}(T)$
defined in Definition 8.3, which is why we use that distribution.

Since $\bm{X}$ is drawn from a product distribution, and $\bm{z}_{i}$ depends
on only the $i^{\text{th}}$ coordinate of $\bm{X}$,
$\bm{z}_{1},\ldots,\bm{z}_{k}$ are independent. Furthermore, each has mean
$\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mu}[H(\bm{x})]=\delta$. Therefore,
$\sum_{i\in[k]}\bm{z}_{i}$ is distributed according to
$\mathrm{Bin}(k,\delta)$. ∎

A couple of remarks about the above Lemma: First, it implies that
$\mathrm{Dens}_{H}(\bm{\ell})$ concentrates around $\delta k$. Since $z\mapsto
e^{\lambda z}$ is convex for any $\lambda\in\mathds{R}$, Lemma 8.4 implies
that the moment generating function of $\mathrm{Dens}_{H}(\bm{\ell})$ is
dominated by that of $\mathrm{Bin}(k,\delta)$. This means that Chernoff bounds
that hold for $\mathrm{Bin}(k,\delta)$ also hold for
$\mathrm{Dens}_{H}(\bm{\ell})$. In particular, the statement of Lemma 5.8 is a
consequence of the Chernoff bound given in Fact 7.3.

Second, the proof of Lemma 8.4 does not make heavy use of the decision tree
structure of $T$. It only uses that the leaves of $T$ partition $(\\{\pm
1\\}^{n})^{k}$, and so may find uses for other models that partition the
domain.

##### Depth amplification for hardcore advantage.

While the resilience lemma gives a fairly fine-grained understanding of how
hardcore density distributes among the leaves, our guarantee for hardcore
advantage are more coarse – that its expectation over the leaves is bounded.

######  Definition 8.5 (Hardcore advantage at $\ell$, Definition 5.4
restated).

For any tree $T:(\\{\pm 1\\}^{n})^{k}\to\\{\pm 1\\}^{k}$, hardcore measure
$H:\\{\pm 1\\}^{n}\to[0,1]$, distribution $\mu$ on $\\{\pm 1\\}^{n}$,
$i\in[k]$, and leaf $\ell$ of $T$, the hardcore advantage at $\ell$ in the
$i$th block is the quantity:

$\mathrm{Adv}_{H}(\ell,i)\coloneqq\Big{|}\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}\big{[}f(\bm{X}^{(i)})T(\bm{X})_{i}H(\bm{X}^{(i)})\mid\text{$\bm{X}$
reaches $\ell$}\big{]}\Big{|}.$ (9)

The total hardcore advantage at $\ell$ is the quantity
$\displaystyle\mathrm{Adv}_{H}(\ell)\coloneqq\sum_{i=1}^{k}\mathrm{Adv}_{H}(\ell,i).$

######  Lemma 8.6 (Expected total hardcore advantage, 5.7 restated).

If $H$ is a $(\gamma,d)$-hardcore measure for $f$ of density $\delta$ w.r.t.
$\mu$ and the expected depth of $T$ is at most $dk$, then

$\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}[\mathrm{Adv}_{H}(\bm{\ell})]\leq\gamma\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}[\mathrm{Dens}_{H}(\bm{\ell})]=\gamma\delta
k.$

###### Proof of Lemma 8.6.

By contrapositive. Suppose there exists $T_{\textnormal{large}}:(\\{\pm
1\\}^{n})^{k}\to\\{\pm 1\\}^{k}$ making $dk$ queries on average w.r.t.
$\mu^{k}$ for which,

$\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}[\mathrm{Adv}_{H}(\bm{\ell})]>\gamma\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}[\mathrm{Dens}_{H}(\bm{\ell})]=\gamma\delta
k.$

Then, we’ll show there exists $T_{\textnormal{small}}:\\{\pm 1\\}^{n}\to\\{\pm
1\\}$ making $d$ queries on average w.r.t. $\mu$ for which

$\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mu}[f(\bm{x})T_{\textnormal{small}}(\bm{x})H(\bm{x})]>\gamma\cdot\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mu}[H(\bm{x})]=\gamma\delta.$

Before constructing $T_{\textnormal{small}}$, we observe that we can assume,
without loss of generality, that for every leaf $\ell$ of $T$, that we can
remove the absolute value from Equation 9; i.e. that

$\mathrm{Adv}_{H}(\ell,i)=\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}\big{[}f(\bm{X}^{(i)})T(\bm{X})_{i}H(\bm{X}^{(i)})\mid\text{$\bm{X}$
reaches $\ell$}\big{]}$

Otherwise, we could modify this leaf by flipping the label of $T(X)_{i}$
whenever $X$ reaches a leaf where the above quantity is negative. This does
not change the hardcore advantage, so this new $T$ still satisfies our
assumption.

$T_{\textnormal{small}}$ will be a randomized algorithm. Upon receiving the
input $x\in\\{\pm 1\\}^{n}$, it samples $\bm{X}\sim\mu^{k}$ and
$\bm{i}\sim\mathrm{Unif}([k])$, and then constructs $\bm{X}(x,\bm{i})$ by
inserting $x$ into the $\bm{i}^{\text{th}}$ block of $\bm{X}$,

$(\bm{X}(x,i))^{(j)}=\begin{cases}\bm{X}^{(j)}&\text{if }j\neq i\\\ x&\text{if
}j=\bm{i}.\end{cases}$

Then, $T_{\textnormal{small}}(x)$ outputs
$T_{\textnormal{large}}(\bm{X}(x,\bm{i}))_{\bm{i}}$.

Our analysis of $T_{\textnormal{small}}$ relies on the following simple
observation: If we sample $\bm{x}\sim\mu$, then even conditioning on any
choice of $\bm{i}=i$, the distribution of $\bm{X}(\bm{x},\bm{i})$ is
$\mu^{k}$. This also means that $\bm{X}(\bm{x},\bm{i})$ and $\bm{i}$ are
independent.

We claim that $T_{\textnormal{small}}$ has the two desired properties; low
expected number of queries, and high accuracy on $H$. To bound the expected
number of queries $T_{\textnormal{small}}$ makes on an input $\bm{x}\sim\mu$,
we use that $\bm{X}(\bm{x},\bm{i})$ is distributed according to $\mu^{k}$.
Therefore, $T_{\textnormal{large}}(\bm{X}(\bm{x},\bm{i}))$ makes, on average,
$dk$ queries. Expanded, we have that,

$\sum_{i\in[k],j\in[n]}\operatorname{{Pr}}[T_{\textnormal{large}}(\bm{X}(\bm{x},\bm{i}))\text{
queries }\bm{X}(\bm{x})^{(i)}_{j}]=dk.$

Whereas, the number of queries $T_{\textnormal{small}}(\bm{x})$ makes only
counts queries to the $\bm{i}^{\text{th}}$ block, and is therefore,

$\displaystyle\sum_{i\in[k],j\in[n]}\operatorname{{Pr}}\big{[}T_{\textnormal{large}}(\bm{X}(\bm{x},\bm{i}))$
$\displaystyle\text{ queries
}\bm{X}(\bm{x},\bm{i})^{(i)}_{j}\cdot\mathds{1}[\bm{i}=i]\big{]}$
$\displaystyle=\sum_{i\in[k],j\in[n]}\operatorname{{Pr}}\big{[}T_{\textnormal{large}}(\bm{X}(\bm{x},\bm{i})))\text{
queries }\bm{X}(\bm{x},\bm{i})^{(i)}_{j}\big{]}\cdot\frac{1}{k}$
$\displaystyle=d.$

In the above, the first equality uses that $\bm{i}$ is independent of
$\bm{X}(\bm{x},\bm{i})$, and so is still uniform on $[k]$ even conditioned on
which queries $T_{\textnormal{large}}$ makes.

Lastly, we verify that $T_{\textnormal{small}}$ has high accuracy on the
hardcore measure.

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mu}[f(\bm{x})T_{\textnormal{small}}(\bm{x},\bm{i}))H(\bm{x})]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mu}[f(\bm{x})T_{\textnormal{large}}(\bm{X}(\bm{x},\bm{i})))_{\bm{i}}H(\bm{x})]$
(Definition of $T_{\textnormal{small}}$)
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{i}\sim[k]}\left[\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}\left[f(\bm{X}^{(\bm{i})})T_{\textnormal{large}}(\bm{X})_{\bm{i}}H(\bm{X}^{(\bm{i})})\right]\right]$
($\bm{i},\bm{X}(\bm{x})$ are independent)
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{i}\sim[k]}\left[\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T_{\textnormal{large}})}[\mathrm{Adv}_{H}(\bm{\ell},\bm{i})]\right]$
(Definition 8.5)
$\displaystyle=\frac{1}{k}\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T_{\textnormal{large}})}[\mathrm{Adv}_{H}(\bm{\ell})]>\gamma\delta.$
∎

###  8.3 Understanding the error in terms of hardcore density and advantage

To state the main result of this subsection, we’ll define the following
distribution for the sum of independent Bernoulli random variables.

######  Definition 8.7.

For any $p\in[0,1]^{k}$, we use $\mathrm{BerSum}(p)$ to denote the
distribution of $\bm{z}\coloneqq\bm{z}_{1}+\cdots+\bm{z}_{k}$ where each
$\bm{z}_{i}$ is independently drawn from $\mathrm{Ber}(p_{i})$.

The following generalizes Lemma 5.5.

######  Lemma 8.8 (Accuracy in terms of hardcore density and advantage of the
leaves).

Let $H$ be a $(\gamma,d)$-hardcore measure w.r.t. $\mu$ for $f:\\{\pm
1\\}^{n}\to\\{\pm 1\\}$, and $T:(\\{\pm 1\\}^{n})^{k}\to\\{\pm 1\\}$ be any
tree. Then, for any $t\geq 0$,

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{X}\sim\mu^{k}}\left[\big{\|}T(\bm{X})-f^{\otimes
k}(\bm{X})\big{\|}_{0}\leq
t\right]\leq\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\left[\mathop{{\operatorname{{Pr}}}\/}_{\bm{z}\sim\mathrm{BerSum}(p(\bm{\ell}))}[\bm{z}\leq
t]\right]$

where $p(\ell)\in[0,1]^{k}$ is the vector where

$p(\ell)_{i}\coloneqq\frac{\mathrm{Dens}_{H}(\ell,i)-\mathrm{Adv}_{H}(\ell,i)}{2}\quad\quad\text{for
each }i\in[k].$

Lemma 8.8 implies a generalization of Lemma 5.5.

######  Corollary 8.9.

Let $H$ be a $(\gamma,d)$-hardcore measure w.r.t. $\mu$ for $f:\\{\pm
1\\}^{n}\to\\{\pm 1\\}$, and $T:(\\{\pm 1\\}^{n})^{k}\to\\{\pm 1\\}$ be any
tree. Then, for any $t\geq 0$,

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{X}\sim\mu^{k}}\Big{[}\big{\|}T(\bm{X})-f^{\otimes
k}(\bm{X})\big{\|}_{0}\leq
t\Big{]}\leq\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\left[\min\Big{(}1,\exp\Big{(}t-\frac{\mathrm{Dens}_{H}(\bm{\ell})-\mathrm{Adv}_{H}(\bm{\ell})}{4}\Big{)}\Big{)}\right].$

###### Proof.

The Chernoff bound of Fact 7.3 says that, for any $p\in[0,1]^{k}$ and
$\mu\coloneqq\sum_{i\in[k]}p_{i}$,

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{z}\sim\mathrm{BerSum}(p)}[\bm{z}\leq
t]\leq\begin{cases}\exp\left(-\frac{(\mu-t)^{2}}{2\mu}\right)&\text{if
}\mu\geq t\\\ 1&\text{otherwise.}\end{cases}$

We want to show that the above is bounded by $\min(1,e^{t-\mu/2})$. Clearly
this holds for $\mu<t$, so we need only consider the case where $\mu\geq t$

$\exp\left(-\tfrac{(\mu-t)^{2}}{2\mu}\right)=\exp\left(-\tfrac{\mu^{2}-2t\mu+t^{2}}{2\mu}\right)\leq\exp\left(-\tfrac{\mu^{2}-2t\mu}{2\mu}\right)=e^{t-\mu/2}.$

Since $\exp\left(-\frac{(\mu-t)^{2}}{2\mu}\right)\leq 1$ as well, it is upper
bounded by $\min(1,e^{t-\mu/2})$ as desired. The desired result follows from
Lemma 8.8 as well as
$\sum_{i\in[k]}p(\ell)_{i}=\frac{\mathrm{Dens}_{H}(\ell)-\mathrm{Adv}_{H}(\ell)}{2}$
for every leaf $\ell$ of $T$. ∎

The main observation underlying Lemma 8.8 is that, if we choose an input
$\bm{X}\sim\mu^{k}$ conditioned on reaching a leaf $\ell\in T$, that $\bm{X}$
is distributed according to a $k$-wise product distribution (i.e. from
$\mu_{1}(\ell)\times\cdots\times\mu_{k}(\ell)$ for appropriately defined
distributions). The below is essentially the same as Lemma 3.2 of [Dru12], but
we include a proof for completeness.

######  Claim 8.10.

For any (potentially randomized) tree $T:(\\{\pm 1\\}^{n})^{k}\to\mathcal{Y}$
and leaf $\ell$ of $T$, if $\bm{X}\sim\mu^{k}$, then the distribution of
$\bm{X}$ conditioned on reaching the leaf $\ell$ is a product distribution
over the $k$ blocks of $\bm{X}$.

###### Proof.

First, if $T$ is a randomized tree, it is as a distribution over deterministic
trees. If the desired result holds for each of those deterministic trees, it
also holds for $T$. Therefore, it suffices to consider the case where $T$ is
deterministic.

We’ll prove that the distribution of $\bm{X}$ reaching any internal node _or_
leaf of $T$ is product by induction on the depth of that node. If that depth
is $0$, then all inputs reach it and so the desired result follows from
$\mu^{k}$ being product.

For depth $d\geq 1$, let $\alpha$ be the parent of $\ell$. Then $\alpha$ has
depth $d-1$, so by the inductive hypothesis, the distribution of inputs
reaching $\alpha$ is product. Let $i\in[k],j\in[n],b\in\\{\pm 1\\}$ be chosen
so that an input $X$ reaches $\ell$ iff it reaches $\alpha$ and
$X^{(i)}_{j}=b$. Then,

$\displaystyle\operatorname{{Pr}}[$ $\displaystyle\bm{X}=X\mid\bm{X}\text{
reaches }\ell]$ $\displaystyle=\operatorname{{Pr}}[\bm{X}=X\mid\bm{X}\text{
reaches
}\alpha]\cdot\frac{\mathds{1}[X^{(i)}_{j}=b]}{\operatorname{{Pr}}[X^{(i)}_{j}=b\mid\bm{X}\text{
reaches }\alpha]}$
$\displaystyle=\frac{\mathds{1}[X^{(i)}_{j}=b]}{\operatorname{{Pr}}[X^{(i)}_{j}=b\mid\bm{X}\text{
reaches
}\alpha]}\cdot\prod_{\ell\in[k]}\operatorname{{Pr}}[\bm{X}^{(\ell)}=X^{(\ell)}\mid\bm{X}\text{
reaches }\alpha]$ (Inductive hypothesis) $\displaystyle=\left(\prod_{\ell\neq
i}\operatorname{{Pr}}[\bm{X}^{(\ell)}=X^{(\ell)}\mid\bm{X}\text{ reaches
}\alpha]\right)\cdot\frac{\operatorname{{Pr}}[\bm{X}^{(i)}=X^{(i)}\mid\bm{X}\text{
reaches
}\alpha]\cdot\mathds{1}[X^{(i)}_{j}=b]}{\operatorname{{Pr}}[X^{(i)}_{j}=b\mid\bm{X}\text{
reaches }\alpha]}$ $\displaystyle=\left(\prod_{\ell\neq
i}\operatorname{{Pr}}[\bm{X}^{(\ell)}=X^{(\ell)}\mid\bm{X}\text{ reaches
}\alpha]\right)\cdot\operatorname{{Pr}}[\bm{X}^{(i)}=X^{(i)}\mid\bm{X}\text{
reaches }\alpha,\bm{X}^{(i)}_{j}=b].$

The above is decomposed as a product over the $k$ components of $X$, so is a
product distribution. ∎

We conclude this subsection with a proof of Lemma 8.8.

###### Proof of Lemma 8.8.

Consider any leaf $\ell$ of $T$. We wish to compute the probability that
$T(\bm{X})$ makes less than $t$ mistakes on $f^{\otimes k}(\bm{X})$ given that
$\bm{X}$ reaches the leaf $\ell$. On this leaf, $T$ outputs a single vector
$y\in\\{\pm 1\\}^{k}$. Meanwhile, by 8.10, the distribution of $\bm{X}$ is
product over the blocks, and so $f(\bm{X}^{(1)}),\ldots,f(\bm{X}^{(k)})$ are
independent. Define $q(\ell)\in[0,1]^{k}$ as,

$q(\ell)_{i}\coloneqq\mathop{{\operatorname{{Pr}}}\/}_{\bm{X}\sim\mu^{k}}[y_{i}\neq
f(\bm{X}^{(i)})].$

Then,

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{X}\sim\mu^{k}}\big{[}\big{\|}T(\bm{X}),f^{\otimes
k}(\bm{X})\big{\|}_{0}\leq t\mid\bm{X}\text{ reaches
}\ell\big{]}=\mathop{{\operatorname{{Pr}}}\/}_{\bm{z}\sim\mathrm{BerSum}(q(\ell))}[\bm{z}\leq
t].$

For $\bm{z}\sim\mathrm{BerSum}(q)$, the probability $\bm{z}\leq t$ is
monotonically decreasing in each $q_{i}$. Therefore, it suffices to show that
$q(\ell)_{i}\geq p(\ell)_{i}$ for each $i\in[k]$. We compute,

$\displaystyle q(\ell)_{i}$
$\displaystyle=\mathop{{\operatorname{{Pr}}}\/}_{\bm{X}\sim\mu^{k}}[T(\bm{X})_{i}\neq
f(\bm{X}^{(i)})\mid\bm{X}\text{ reaches }\ell]$
$\displaystyle=\frac{1-\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}[T(\bm{X})_{i}f(\bm{X}^{(i)})\mid\bm{X}\text{
reaches }\ell]}{2}$ ($T(X)_{i},f(X^{(i)}\in\\{\pm 1\\}$)

Separating the above expectation into two pieces, for $\bm{X}$ drawn from
$\mu^{k}$ conditioned in $\bm{X}$ reaching $\ell$,

$\displaystyle\mathop{{\mathds{E}}\/}[T(\bm{X})_{i}f(\bm{X}^{(i)})]$
$\displaystyle=\mathop{{\mathds{E}}\/}[T(\bm{X})_{i}f(\bm{X}^{(i)})H(\bm{X}^{(i)})]+\mathop{{\mathds{E}}\/}[T(\bm{X})_{i}f(\bm{X}^{(i)})(1-H(\bm{X}^{(i)}))]$
$\displaystyle\leq\mathrm{Adv}_{H}(\ell,i)+\mathop{{\mathds{E}}\/}[T(\bm{X})_{i}f(\bm{X}^{(i)})(1-H(\bm{X}^{(i)}))]$
(Definition 5.4)
$\displaystyle\leq\mathrm{Adv}_{H}(\ell,i)+\mathop{{\mathds{E}}\/}[(1-H(\bm{X}^{(i)}))]=1+\mathrm{Adv}_{H}(\ell,i)-\mathrm{Dens}_{H}(\ell,i).$

Therefore,

$q(\ell)_{i}\geq\frac{\mathrm{Dens}_{H}(\ell,i)-\mathrm{Adv}_{H}(\ell,i)}{2}=p(\ell)_{i}.\qed$

###  8.4 Completing the proof of the threshold direct sum theorem

In this subsection, we complete the proof of Theorem 6. Throughout this
section, we’ll use the following function:

$g_{t}(z)\coloneqq\min(1,e^{t-z/4}).$

By using Corollary 8.9, it suffices to show that

$\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\left[g_{\delta
k/10}(\mathrm{Dens}_{H}(\bm{\ell})-\mathrm{Adv}_{H}(\bm{\ell}))\right]\leq
e^{-\delta k/10}+1-\gamma.$ (10)

Recall that we have much information about how $\mathrm{Dens}_{H}(\bm{\ell})$
distributes over the leaves via Lemma 8.4, but a coarser understanding of how
$\mathrm{Adv}_{H}(\bm{\ell})$ distributes via Lemma 8.6. Because of this, we
will first bound the above equation where the $\mathrm{Adv}_{H}(\bm{\ell})$ is
set to $0$ and analyze how much including that term affects the result.

######  Lemma 8.11.

For any tree $T:(\\{\pm 1\\}^{n})^{k}\to\\{\pm 1\\}^{k}$ and hardcore measure
of density $\delta$ w.r.t. distribution $\mu$,

$\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\left[g_{\delta
k/10}(\mathrm{Dens}_{H}(\bm{\ell}))\right]\leq e^{-.121\delta k}.$

###### Proof.

We bound,

$\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\left[\min\Big{(}1,\exp\Big{(}\delta
k/10-\frac{\mathrm{Dens}_{H}(\bm{\ell})}{4}\Big{)}\Big{)}\right]\leq e^{\delta
k/10}\cdot\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\left[e^{-\mathrm{Dens}_{H}(\ell)/4}\right].$

Since $z\mapsto e^{-z/4}$ is convex, we can use Lemma 8.4 to bound the above
using the moment generating function of the binomial distribution,

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\left[e^{-\mathrm{Dens}_{H}(\bm{\ell})/4}\right]$
$\displaystyle\leq\mathop{{\mathds{E}}\/}_{\bm{z}\sim\mathrm{Bin}(k,\delta)}[e^{-\bm{z}/4}]$
$\displaystyle=(1-\delta(1-e^{-1/4}))^{k}$ $\displaystyle\leq
e^{-(1-e^{-1/4})\delta k}.$

Combining the above,

$\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\left[g_{\delta
k/10}(\mathrm{Dens}_{H}(\bm{\ell}))\right]\leq e^{-\delta
k(1-e^{-1/4}-1/10)}\leq e^{-0.121\delta k}.\qed$

Next, we prove a Lipschitz-style bound for $g$. This will be useful in
incorporating $\mathrm{Adv}_{H}(\bm{\ell})$ to Equation 10.

######  Proposition 8.12.

For any $z,\Delta,t\geq 0$,

$g_{t}(z-\Delta)\leq g_{t}(z)+\Delta/4.$ (11)

Furthermore, if $z\geq 5t$, then

$g_{t}(z-\Delta)\leq g_{t}(z)+\Delta/t.$ (12)

###### Proof.

Equation 11 follows from the $(1/4)$-Lipschitzness of $g_{t}(z)$.

For Equation 12, fix any choice of $z\geq 5t$. We want to show that for any
choice of $\Delta$,

$\frac{g_{t}(z-\Delta)-g_{t}(z)}{\Delta}\leq 1/t.$

We claim that the left hand side of the above inequality is maximized when
$\Delta=z-4t$. When $\Delta$ is increased beyond $z-4t$, the numerator remains
constant (because $g_{t}(z)$ is constant for any $z\leq 4t$, but the
denominator increases, so the maximum cannot occur at at any $\Delta>z-4t$. On
the other hand, $g_{t}(z)$ is convex when restricted to the domain
$[4t,\infty)$, so the maximum cannot occur at any $\Delta<z-4t$. Therefore, it
suffices to consider $\Delta=z-4t$, in which case,

$\frac{g_{t}(z-\Delta)-g_{t}(z)}{\Delta}=\frac{1-g_{t}(z)}{\Delta}\leq\frac{1}{\Delta}\leq
1/t.\qed$

We are now ready to prove the main result of this section.

###### Proof of Theorem 6.

By applying Corollary 8.9,

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{X}\sim\mu^{k}}\left[\big{\|}T(\bm{X})-f^{\otimes
k}(\bm{X})\big{\|}_{0}\leq\delta
k/10\right]\leq\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\left[g_{\delta
k/10}(\mathrm{Dens}_{H}(\bm{\ell})-\mathrm{Adv}_{H}(\bm{\ell}))\right].$

First, we consider the case where $\delta k\leq 40$. Here, by applying
Equation 11,

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\left[g_{\delta
k/10}(\mathrm{Dens}_{H}(\bm{\ell})-\mathrm{Adv}_{H}(\bm{\ell}))\right]$
$\displaystyle\leq\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\left[g_{\delta
k/10}(\mathrm{Dens}_{H}(\bm{\ell}))\right]+\tfrac{1}{4}\cdot\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}[\mathrm{Adv}_{H}(\bm{\ell})]$
$\displaystyle\leq e^{-0.121\delta k}+\gamma\delta k/4$ (Lemmas 8.11 and 8.6)
$\displaystyle\leq e^{-\delta k/10}+10\gamma$ ($\delta k\leq 40$)

When $\delta k>40$, we break down the desired result into two pieces,
depending on whether $\mathrm{Dens}_{H}(\bm{\ell})$ is small or large. For the
piece where $\mathrm{Dens}_{H}(\bm{\ell})$ is small, we just use that
$g(\cdot)$ is bounded between $0$ and $1$ which means $g(z)-g(z-\Delta)\leq
1$,

$\displaystyle\mathop{{\mathds{E}}\/}\big{[}g_{\delta
k/10}(\mathrm{Dens}_{H}(\bm{\ell})$
$\displaystyle-\mathrm{Adv}_{H}(\bm{\ell}))\cdot\mathds{1}[\mathrm{Dens}_{H}(\bm{\ell})\leq\delta
k/2]\big{]}$ $\displaystyle\leq\mathop{{\mathds{E}}\/}\left[g_{\delta
k/10}(\mathrm{Dens}_{H}(\bm{\ell}))\cdot\mathds{1}[\mathrm{Dens}_{H}(\bm{\ell})\leq\delta
k/2]\right]+\operatorname{{Pr}}[\mathrm{Dens}_{H}(\bm{\ell})\leq\delta k/2]$
$\displaystyle\leq\mathop{{\mathds{E}}\/}\left[g_{\delta
k/10}(\mathrm{Dens}_{H}(\bm{\ell}))\cdot\mathds{1}[\mathrm{Dens}_{H}(\bm{\ell})\leq\delta
k/2]\right]+e^{-\delta k/8}.$ (Lemma 5.8)

For the piece where $\mathrm{Dens}_{H}(\bm{\ell})$ is large, we use Equation
12

$\displaystyle\mathop{{\mathds{E}}\/}\big{[}g_{\delta k/10}$
$\displaystyle(\mathrm{Dens}_{H}(\bm{\ell})-\mathrm{Adv}_{H}(\bm{\ell}))\cdot\mathds{1}[\mathrm{Dens}_{H}(\bm{\ell})>\delta
k/2]\big{]}$ $\displaystyle\leq\mathop{{\mathds{E}}\/}\left[g_{\delta
k/10}(\mathrm{Dens}_{H}(\bm{\ell}))\cdot\mathds{1}[\mathrm{Dens}_{H}(\bm{\ell})>\delta
k/2]\right]+\tfrac{10}{\delta
k}\cdot\mathop{{\mathds{E}}\/}\left[\mathrm{Adv}_{H}(\bm{\ell})\cdot\mathds{1}[\mathrm{Dens}_{H}(\bm{\ell})>\delta
k/2]\right]$ (Equation 12)
$\displaystyle\leq\mathop{{\mathds{E}}\/}\left[g_{\delta
k/10}(\mathrm{Dens}_{H}(\bm{\ell}))\cdot\mathds{1}[\mathrm{Dens}_{H}(\bm{\ell})>\delta
k/2]\right]+\tfrac{10}{\delta
k}\cdot\mathop{{\mathds{E}}\/}\left[\mathrm{Adv}_{H}(\bm{\ell})\right]$
($\mathrm{Dens}_{H}(\bm{\ell})\geq 0$)
$\displaystyle\leq\mathop{{\mathds{E}}\/}\left[g_{\delta
k/10}(\mathrm{Dens}_{H}(\bm{\ell}))\cdot\mathds{1}[\mathrm{Dens}_{H}(\bm{\ell})>\delta
k/2]\right]+\tfrac{10}{\delta k}\cdot\gamma\delta k$ (Lemma 8.6)

Combining the above two pieces,

$\displaystyle\mathop{{\mathds{E}}\/}\big{[}g_{\delta
k/10}(\mathrm{Dens}_{H}(\bm{\ell})-\mathrm{Adv}_{H}(\bm{\ell}))\big{]}$
$\displaystyle\leq\mathop{{\mathds{E}}\/}\big{[}g_{\delta
k/10}(\mathrm{Dens}_{H}(\bm{\ell}))\big{]}+e^{-\delta k/8}+10\gamma$
$\displaystyle\leq e^{-\delta k/8}+e^{-0.121\delta k}+10\gamma$ (Lemma 8.11)

When $\delta k>40$, $e^{-\delta k/8}+e^{-0.121\delta k}<e^{-\delta k/10}$, so
we also recover the desired result in this case. ∎

##  9 Equivalence between direct sum theorems and XOR lemmas and the proof of
Theorem 3

In this section, we prove the following claim which shows that a strong direct
sum theorem implies a strong XOR lemma. We then derive Theorem 3 as a
consequence of this equivalence and our strong direct sum theorem for query
complexity (Theorem 1).

######  Claim 9.1 (Equivalence between direct sum theorems and XOR lemmas).

For every $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, distribution $\mu$ over $\\{\pm
1\\}^{n}$, integer $k\in\mathds{N}$, multiplicative factor $M\in\mathds{R}$,
and $\varepsilon\in(0,1)$, if the following direct sum theorem holds:

$\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\otimes k},\varepsilon)\geq
M\cdot\overline{\mathrm{Depth}}^{\mu}(f,\delta).$

then, the following XOR lemma holds:

$\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\oplus k},\tfrac{\varepsilon}{2})\geq
M\cdot\overline{\mathrm{Depth}}^{\mu}(f,\delta).$

In order to prove 9.1 and Theorem 3, we establish a lemma which allows us to
convert any decision accurately computing $f^{\oplus k}$ into a decision tree
accurately computing $f^{\otimes k}$. The following definition captures this
conversion.

######  Definition 9.2 (The product tree).

Given a decision tree $T:(\\{\pm 1\\}^{n})^{k}\to\\{\pm 1\\}$, the $k$-wise
product tree $\tilde{T}:(\\{\pm 1\\}^{n})^{k}\to\\{\pm 1\\}^{k}$ is defined as
follows. For the internal nodes, $\tilde{T}$ has exactly the same structure as
$T$. For a leaf $\ell$ in $T$, the leaf vector
$(\ell_{1},\ldots,\ell_{k})\in\\{\pm 1\\}^{k}$ in $\tilde{T}$ is defined by

$\ell_{i}\coloneqq\mathrm{sign}\left(\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}[f(\bm{X}^{(i)})\mid\bm{X}\text{
reaches }\ell]\right)$

for all $i\in[k]$.

Intuitively, $\tilde{T}$ computes $T$’s best guess for $f(X^{(i)})$ for each
$i\in[k]$ on a given input $(X^{(1)},\ldots,X^{(k)})$. If $T$ is really good
at computing $f^{\oplus k}$ then at every leaf it should have queried enough
variables to pin down $f$’s value on each of the input blocks. The main lemma
formalizes this intuition.

######  Lemma 9.3.

For any $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, distribution $\mu$ over $\\{\pm
1\\}^{n}$, and tree $T:(\\{\pm 1\\}^{n})^{k}\to\\{\pm 1\\}$, the $k$-wise
product tree $\tilde{T}:(\\{\pm 1\\}^{n})^{k}\to\\{\pm 1\\}^{k}$ satisfies

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{X}\sim\mu^{k}}[\tilde{T}(\bm{X})=f^{\otimes
k}(\bm{X})]\geq\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}[T(\bm{X})f^{\oplus
k}(\bm{X})].$

###  9.1 Proofs of 9.1 and Theorem 3 assuming Lemma 9.3

The following corollary of Lemma 9.3 implies 9.1 and Theorem 3.

######  Corollary 9.4 (Main corollary of Lemma 9.3).

For all $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$, $k\geq 1$, distributions $\mu$ over
$\\{\pm 1\\}^{n}$, and $\varepsilon>0$,
$\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\oplus
k},\frac{\varepsilon}{2})\geq\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\otimes
k},\varepsilon)$.

###### Proof.

Let $\bm{A}$ be a randomized query algorithm for $f^{\oplus k}$ with error
$\varepsilon/2$ and expected cost
$q=\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\oplus k},\varepsilon/2)$. Let
$\mathcal{T}$ denote the distribution over decision trees determined by
$\bm{A}$. Consider the algorithm $\tilde{\bm{A}}$ which computes $f^{\otimes
k}(X)$ by sampling ${\bm{T}}\sim\mathcal{T}$ and returning
$\tilde{{\bm{T}}}(X)$ where $\tilde{{\bm{T}}}$ is the decision tree from Lemma
9.3. Then, the success of $\tilde{\bm{A}}$ is

$\displaystyle\mathop{{\mathds{E}}\/}_{{\bm{T}}\sim\mathcal{T}}\left[\mathop{{\operatorname{{Pr}}}\/}_{\bm{X}\sim\mu^{k}}[\tilde{{\bm{T}}}(\bm{X})=f^{\otimes
k}(\bm{X})]\right]$
$\displaystyle\geq\mathop{{\mathds{E}}\/}_{{\bm{T}}\sim\mathcal{T}}\left[\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}[{\bm{T}}(\bm{X})f^{\oplus
k}(\bm{X})]\right]$ (Lemma 9.3) $\displaystyle\geq 1-\varepsilon$

where the last step uses the fact that advantage is $1-2\cdot\mathrm{error}$.
Since the structure of each $\tilde{T}$ is the same as $T$, the expected cost
of $\tilde{\bm{A}}$ is $q$ which completes the proof. ∎

###### Proofs of 9.1 and Theorem 3.

By Corollary 9.4,

$\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\oplus
k},\tfrac{\varepsilon}{2})\geq\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\otimes
k},\varepsilon)\geq M\cdot\overline{\mathrm{Depth}}^{\mu}(f,\delta).$

Theorem 3 follows immediately by applying 9.1 to Theorem 2. ∎

######  Remark 9.5 (On the necessity of the $1/2$ loss in $\varepsilon$ in
Corollary 9.4).

One may wonder whether the $1/2$ loss in $\varepsilon$ parameter in Corollary
9.4 is necessary. For example, can one show
$\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\oplus
k},0.51\varepsilon)\geq\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\otimes
k},\varepsilon)$? The issue is that
$\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\oplus k},0.5)=0$ for all functions
$f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ because the bias of $f^{\oplus k}$ is at
least $0.5$. So such a statement cannot hold for all $f$ in all parameter
regimes. Concretely, one can show that if $f$ is the parity of $n$ bits and
$\mu$ is uniform over $\\{\pm 1\\}^{n}$, then
$\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\otimes k},\varepsilon)\geq\Omega(kn)$
for all constant $\varepsilon<1$. Any path in a decision tree for $f^{\otimes
k}$ which queries at most $\lambda kn$ bits for some constant $\lambda<1$ has
success probability $2^{-\Omega(k)}$. So to achieve any constant accuracy
requires $\Omega(kn)$ expected depth. On the other hand,
$\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\oplus
k},0.5)=1\ll\overline{\mathrm{Depth}}^{\mu^{k}}(f^{\otimes k},\varepsilon)$
which is achieved by the decision tree that outputs a single constant value.
Therefore, the $\varepsilon/2$ in Corollary 9.4 is necessary for such a
statement to hold in full generality.

###  9.2 Proof of Lemma 9.3

Each $\ell_{i}$ for $i\in[k]$ satisfies

$\displaystyle\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}[\ell_{i}\cdot
f(\bm{X}^{(i)})\mid\bm{X}\text{ reaches }\ell]$
$\displaystyle=\left|\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}[f(\bm{X}^{(i)})\mid\bm{X}\text{
reaches }\ell]\right|$
$\displaystyle\geq\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}[\ell\cdot
f(\bm{X}^{(i)})\mid\bm{X}\text{ reaches }\ell].$

In particular, for all leaves $\ell$ of $T$,

$\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}[\tilde{T}(\bm{X})_{i}\cdot
f(\bm{X}^{(i)})\mid\bm{X}\text{ reaches
}\ell]\geq\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}[T(\bm{X})\cdot
f(\bm{X}^{(i)})\mid\bm{X}\text{ reaches }\ell].$ (13)

Therefore:

$\displaystyle\mathop{{\operatorname{{Pr}}}\/}_{\bm{X}\sim\mu^{k}}$
$\displaystyle[\tilde{T}(\bm{X})=f^{\otimes k}(\bm{X})]$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\bigg{[}\mathop{{\operatorname{{Pr}}}\/}_{\bm{X}\sim\mu^{k}}[\tilde{T}(\bm{X})=f^{\otimes
k}(\bm{X})\mid\bm{X}\text{ reaches }\bm{\ell}]\bigg{]}$
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\bigg{[}\prod_{i\in[k]}\mathop{{\operatorname{{Pr}}}\/}_{\bm{X}\sim\mu^{k}}[\tilde{T}(\bm{X})_{i}=f(\bm{X}^{(i)})\mid\bm{X}\text{
reaches }\bm{\ell}]\bigg{]}$ (8.10)
$\displaystyle\geq\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\bigg{[}\prod_{i\in[k]}\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}[\tilde{T}(\bm{X})_{i}f(\bm{X}^{(i)})\mid\bm{X}\text{
reaches }\bm{\ell}]\bigg{]}$
$\displaystyle\geq\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\bigg{[}\prod_{i\in[k]}\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}[T(\bm{X})f(\bm{X}^{(i)})\mid\bm{X}\text{
reaches }\bm{\ell}]\bigg{]}$ (Equation 13)
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\bigg{[}\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}\bigg{[}T(\bm{X})\prod_{i\in[k]}f(\bm{X}^{(i)})\mid\bm{X}\text{
reaches }\bm{\ell}\bigg{]}\bigg{]}$ (8.10)
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{\ell}\sim\mu^{k}(T)}\bigg{[}\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}[T(\bm{X})f^{\otimes
k}(\bm{X})\mid\bm{X}\text{ reaches }\bm{\ell}]\bigg{]}$
($\prod_{i\in[k]}f(\bm{X}^{(i)})=f^{\oplus k}(\bm{X})$)
$\displaystyle=\mathop{{\mathds{E}}\/}_{\bm{X}\sim\mu^{k}}[T(\bm{X})f^{\oplus
k}(\bm{X})]$

which completes the proof. ∎

##  10 Proof of 4.1

######  Claim 10.1 (The $\gamma$ factor in Theorem 2 is necessary; 4.1
restated).

Let $\mathsf{Par}:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ be the parity function and
$\mu$ be the uniform distribution over $\\{\pm 1\\}^{n}$. Then for all
$\gamma$,

$\overline{\mathrm{Depth}}^{\mu^{k}}(\mathsf{Par}^{\otimes k},1-\gamma)\leq
2\gamma k\cdot\overline{\mathrm{Depth}}^{\mu}(\mathsf{Par},\tfrac{1}{4}).$

We will need the following simple proposition, which states that in any tree
that seeks to compute the $n$-variable parity function, leaves of depth
strictly less than $n$ contribute $\frac{1}{2}$ to the error:

######  Proposition 10.2.

For any (potentially randomized) tree $T:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ and
leaf $\ell$ of $T$ with depth strictly less than $n$,

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mathrm{Unif}(\\{\pm
1\\}^{n})}[T(\bm{x})\neq\mathsf{Par}(\bm{x})\mid\bm{x}\text{ reaches
}\ell]=\tfrac{1}{2}.$

###### Proof.

Since $\ell$ is at depth strictly less than $n$, there must be some index
$i\in[n]$ not queried on the path to $\ell$. Taking any input $x$ that reaches
$\ell$, the input $x^{\prime}$ with the $i^{\text{th}}$ bit flipped must also
reach $\ell$ and have the opposite parity. Both of these inputs are equally
likely under the uniform distribution and so the value of
$\mathsf{Par}(\bm{x})$ conditioned on $\bm{x}$ reaching $\bm{\ell}$ is equally
likely to be $+1$ and $-1$. Therefore, $T$ errs half the time it reaches this
leaf regardless of how it labels it. ∎

###### Proof of 10.1.

The proof proceeds in two parts. First, we show that
$\overline{\text{Depth}}^{\mu}(\mathsf{Par},\tfrac{1}{4})=\frac{n}{2}$.
Second, we prove that $\overline{\text{Depth}}^{\mu^{\otimes
k}}(\mathsf{Par}^{\otimes k},1-\gamma)\leq\gamma kn$.

(1) $\overline{\mathrm{Depth}}^{\mu}(\mathsf{Par},\tfrac{1}{4})=\tfrac{n}{2}$.
Let $T$ be an arbitrary randomized decision tree let $p_{n}(T)$ be the
probability that $T$ queries all $n$ variables. Then, the expected depth of
$T$ is at least $n\cdot p_{n}(T)$. Meanwhile, by Proposition 10.2, the error
of $T$ in computing parity is at least $\frac{1}{2}\cdot p_{n}(T)$ w.r.t. the
uniform distribution. Therefore,
$\overline{\text{Depth}}^{\mu}(f,\frac{1}{4})\geq\frac{n}{2}$.

While this direction is not needed for 10.1 we show for completeness that
$\overline{\text{Depth}}^{\mu}(f,\frac{1}{4})\leq\frac{n}{2}$ by constructing
a randomized111At the cost of increasing expected depth by $1$, the tree can
be derandomized. To derandomize it, read a single bit of the input and only
query the rest if that bit is $1$, which occurs with probability
$\tfrac{1}{2}$. decision tree $T$ for $f$. With probability $\frac{1}{2}$, $T$
queries all $n$ variables to compute $f$ exactly. Otherwise, it simply outputs
$0$. $T$ has expected depth $\frac{n}{2}$, and it errs only when it queries no
variables and guesses incorrectly, which happens with probability
$\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{4}$. Thus,
$\overline{\text{Depth}}^{\mu}(f,\frac{1}{4})\leq\frac{n}{2}$.

(2) $\overline{\mathrm{Depth}}^{\mu^{\otimes k}}(f^{\otimes
k},1-\gamma)\leq\gamma kn$. We construct a randomized222Again, this can be
derandomized at the cost of adding $\leq 2$ to the expected depth, since any
biased coin can be simulated with a fair coin using $2$ flips in expectation.
decision tree $T$ for $f^{\otimes k}$. With probability $\gamma$, $T$ queries
all $kn$ variables to compute $f^{\otimes k}$ exactly, and with probability
$1-\gamma$, it outputs 0. When it queries all variables, it has no error so
its average error is at most $1-\gamma$. Furthermore, its average depth is
$\gamma kn$. ∎

## Acknowledgements

We thank William Hoza for a helpful conversation and the CCC reviewers for
their comments and feedback.

The authors are supported by NSF awards 1942123, 2211237, 2224246, a Sloan
Research Fellowship, and a Google Research Scholar Award. Caleb is also
supported by an NDSEG Fellowship, and Carmen by a Stanford Computer Science
Distinguished Fellowship and an NSF Graduate Research Fellowship.

## References

  * [AMRR11] Andris Ambainis, Loïck Magnin, Martin Roetteler, and Jérémie Roland.  Symmetry-assisted adversaries for quantum state generation.  In 2011 IEEE 26th Annual Conference on Computational Complexity (CCC), pages 167–177. IEEE, 2011.
  * [AN21] Sepehr Assadi and Vishvajeet N.  Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma.  In Samir Khuller and Virginia Vassilevska Williams, editors, Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), pages 612–625, 2021.
  * [AŠdW06] Andris Ambainis, Robert Špalek, and Ronald de Wolf.  A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs.  In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pages 618–633, 2006.
  * [BB19] Eric Blais and Joshua Brody.  Optimal Separation and Strong Direct Sum for Randomized Query Complexity.  In 34th Computational Complexity Conference (CCC), volume 137, pages 29:1–29:17, 2019.
  * [BBCR10] Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao.  How to compress interactive communication.  In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pages 67–76, 2010.
  * [BDK18] Shalev Ben-David and Robin Kothari.  Randomized query complexity of sabotaged and composed functions.  Theory of Computing, 14(5):1–27, 2018.
  * [BKLS23] Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn, and Hariharan Srinivasulu.  A strong xor lemma for randomized query complexity.  Theory of Computing, 19(11):1–14, 2023.
  * [BKST23] Guy Blanc, Caleb Koch, Carmen Strassle, and Li-Yang Tan.  A strong composition theorem for junta complexity and the boosting of property testers.  In Proceedings of the 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1757–1777, 2023.
  * [BRWY13] Mark Braverman, Anup Rao, Omri Weinstein, and Amir Yehudayoff.  Direct products in communication complexity.  In Proceedings of the 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 746–755, 2013.
  * [Dru12] Andrew Drucker.  Improved direct product theorems for randomized query complexity.  computational complexity, 21(2):197–244, 2012.
  * [Dru13] Andrew Drucker.  Nondeterministic direct product reductions and the success probability of sat solvers.  In Proceedings of the 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 736–745, 2013.
  * [GNW11] Oded Goldreich, Noam Nisan, and Avi Wigderson.  On yao’s xor-lemma.  Studies in Complexity and Cryptography, 6650:273–301, 2011.
  * [Hoz23] William Hoza.  A technique for hardness amplification against AC0.  ECCC preprint TR23-176, 2023.
  * [IJKW08] Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, and Avi Wigderson.  Uniform direct product theorems: simplified, optimized, and derandomized.  In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pages 579–588, 2008.
  * [Imp95] Russell Impagliazzo.  Hard-core distributions for somewhat hard problems.  In Proceedings of IEEE 36th Annual Foundations of Computer Science (FOCS), pages 538–545, 1995.
  * [IRW94] Russell Impagliazzo, Ran Raz, and Avi Wigderson.  A direct product theorem.  In Proceedings of IEEE 9th Annual Conference on Structure in Complexity Theory, pages 88–96, 1994.
  * [IW97] Russell Impagliazzo and Avi Wigderson.  $\mathrm{P}=\mathrm{BPP}$ if $\mathrm{E}$ requires exponential circuits: Derandomizing the XOR lemma.  In Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC), pages 220–229, 1997.
  * [Jai15] Rahul Jain.  New strong direct product results in communication complexity.  Journal of the ACM (JACM), 62(3):1–27, 2015.
  * [JKS10] Rahul Jain, Hartmut Klauck, and Miklos Santha.  Optimal direct sum results for deterministic and randomized decision tree complexity.  Information Processing Letters, 110(20):893–897, 2010.
  * [JPY12] Rahul Jain, Attila Pereszlényi, and Penghui Yao.  A direct product theorem for the two-party bounded-round public-coin communication complexity.  In Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 167–176, 2012.
  * [Kla10] Hartmut Klauck.  A strong direct product theorem for disjointness.  In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pages 77–86, 2010.
  * [KS03] Adam R Klivans and Rocco A Servedio.  Boosting and hard-core set construction.  Machine Learning, 51:217–238, 2003.
  * [KŠdW07] Hartmut Klauck, Robert Špalek, and Ronald de Wolf.  Quantum and classical strong direct product theorems and optimal time-space tradeoffs.  SIAM Journal on Computing, 36(5):1472–1493, 2007.  Preliminary version in FOCS 2004.
  * [Lev85] Leonid A Levin.  One-way functions and pseudorandom generators.  In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC), pages 363–365, 1985.
  * [LR13] Troy Lee and Jérémie Roland.  A strong direct product theorem for quantum query complexity.  computational complexity, 22:429–462, 2013.
  * [LSŠ08] Troy Lee, Adi Shraibman, and Robert Špalek.  A direct product theorem for discrepancy.  In Proceedings of the 23rd Annual IEEE Conference on Computational Complexity (CCC), pages 71–80, 2008.
  * [NRS94] Noam Nisan, Steven Rudich, and Michael Saks.  Products and help bits in decision trees.  In Proceedings 35th Annual Symposium on Foundations of Computer Science (FOCS), pages 318–329, 1994.
  * [NW94] Noam Nisan and Avi Wigderson.  Hardness vs randomness.  Journal of computer and System Sciences, 49(2):149–167, 1994.
  * [O’D02] Ryan O’Donnell.  Hardness amplification within np.  In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pages 751–760, 2002.
  * [Sha04] Ronen Shaltiel.  Towards proving strong direct product theorems.  Computational Complexity, 12(1/2):1–22, 2004.
  * [She11] Alexander A Sherstov.  Strong direct product theorems for quantum communication and query complexity.  In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pages 41–50, 2011.
  * [Špa08] Robert Špalek.  The multiplicative quantum adversary.  In 23rd Annual IEEE Conference on Computational Complexity (CCC), pages 237–248, 2008.
  * [Str73] Volker Strassen.  Vermeidung von divisionen.  Journal für die reine und angewandte Mathematik, 264:184–202, 1973.
  * [Tre07] Luca Trevisan.  The Impagliazzo Hard-Core-Set Theorem.  https://lucatrevisan.wordpress.com/2007/11/06/the-impagliazzo-hard-core-set-theorem/, 2007\.
  * [VW08] Emanuele Viola and Avi Wigderson.  Norms, xor lemmas, and lower bounds for polynomials and protocols.  Theory of Computing, 4(1):137–168, 2008.
  * [Yao82] Andrew Yao.  Theory and application of trapdoor functions.  In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS), pages 80–91, 1982.
  * [Yu22] Huacheng Yu.  Strong xor lemma for communication with bounded rounds.  In Proceedings of the 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 1186–1192, 2022.

##  Appendix A Figures of stacked and fair trees

$\cdots$$\cdots$$\cdots$$\cdots$$T_{1}$$T_{2}$$T_{2}$$T_{k}$$T_{k}$$T_{k}$depth
$d$

Figure 3: Illustration of a stacked decision tree for a function $f^{\otimes
k}$. The decision tree consists of $k$ depth-$d$ decision trees,
$T_{1},\ldots,T_{k}$, stacked on top of each other. For an input $X\in(\\{\pm
1\\}^{n})^{k}$, the output $T(X)$ is computed sequentially, first by computing
$T_{1}(X)$, then $T_{2}(X)$, and so on. The final output is
$T(X)\coloneqq(T_{1}(X),\ldots,T_{k}(X))$.
$X_{8}^{(i)}$$X_{3}^{(i)}$$X_{22}^{(i)}$$\pi$ $X^{(i)}$ queried $\leq d$ times
on path $\pi$ Figure 4: Illustration of a fair decision tree. For every block
$i\in[k]$ and path $\pi$, the input block $X^{(i)}$ is queried at most $d$
times.

##  Appendix B Proof of Theorem 4

Let $\mathcal{H}$ denote the set of measures of density $\delta/2$ with
respect to $\mu$ and let $\mathcal{T}$ denote the set of decision trees $T$
whose expected depth with respect to $\mu$ is at most $d$. Suppose for
contradiction that there does not exist an $H\in\mathcal{H}$ which is
$(\gamma,d)$-hardcore. That is, for all $H\in\mathcal{H}$ there is a tree $T$
of expected depth at most $d$ satisfying

$\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mu}[f(\bm{x})T(\bm{x})H(\bm{x})]>\gamma\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mu}[H(\bm{x})]=\gamma\delta/2.$
(14)

We use the minimax theorem to switch the quantifiers in the above statement.
Consider the payoff matrix $M$ whose rows are indexed by distributions from
$\mathcal{H}$ and whose columns are indexed by algorithms from $\mathcal{T}$
and whose entries are given by
$M_{H,T}\coloneqq\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mu}[f(\bm{x})T(\bm{x})H(\bm{x})]$.
This is the payoff matrix for the zero-sum game where the row player first
chooses a row $H$ and the column player then chooses a column $T$ and the
payoffs are determined by $M_{H,T}$. Note that once the first player’s
strategy is fixed, we can assume without loss of generality that the second
player’s strategy is deterministic. Therefore, the minimax theorem for zero-
sum games yields

$\displaystyle\gamma\delta/2$
$\displaystyle<\min_{\rho\in\mu(\mathcal{H})}\max_{T\in\mathcal{T}}~{}(\rho^{\top}M)_{T}$
(Equation 14)
$\displaystyle=\max_{\tau\in\mu(\mathcal{T})}\min_{H\in\mathcal{H}}~{}(M\tau)_{H}$
(minimax theorem)

where $\mu(\cdot)$ denotes the set of distributions over a given set.
Therefore, there is a fixed distribution $\tau$ over the set $\mathcal{T}$
such that for all $H\in\mathcal{H}$

$\mathop{{\mathds{E}}\/}_{{\bm{T}}\sim\tau}\bigg{[}\mathop{{\mathds{E}}\/}_{\bm{x}\sim\mu}[f(\bm{x}){\bm{T}}(\bm{x})H(\bm{x})]\bigg{]}>\gamma\delta/2.$
(15)

This shows that

$\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mu}\bigg{[}\mathop{{\mathds{E}}\/}_{{\bm{T}}\sim\tau}[{\bm{T}}(\bm{x})]f(\bm{x})\geq\gamma\bigg{]}\geq
1-\delta/2.$

In particular, if instead
$\mathop{{\operatorname{{Pr}}}\/}_{\bm{x}\sim\mu}[\mathop{{\mathds{E}}\/}_{{\bm{T}}\sim\tau}[{\bm{T}}(\bm{x})]f(\bm{x})<\gamma]\geq\delta/2$
then we can contradict Equation 15 by constructing a $\delta/2$-density $H$
such that $H(x)\coloneqq\operatorname{{Pr}}_{\bm{x}\sim\mu}[\bm{x}=x]$ for a
$\delta/2$-fraction of $x$ satisfying
$\mathop{{\mathds{E}}\/}_{{\bm{T}}\sim\tau}[{\bm{T}}(\bm{x})]f(\bm{x})<\gamma$.
Equation 15 shows that
$\mathop{{\mathds{E}}\/}_{{\bm{T}}\sim\tau}[{\bm{T}}(\bm{x})]$ has good
correlation with $f$ for a large fraction of inputs. We obtain a single
strategy from the distribution $\tau$ by sampling
${\bm{T}}_{1},\ldots,{\bm{T}}_{r}\sim\tau$ for $r$ sufficiently large (chosen
later) and defining $T^{\star}$ as
${\bm{T}}^{\star}(x)\coloneqq\text{MAJ}({\bm{T}}_{1}(x),\ldots,{\bm{T}}_{r}(x))$.
For every $x$ for which
$\mathop{{\mathds{E}}\/}_{{\bm{T}}\sim\tau}[{\bm{T}}(x)]f(x)\geq\gamma$, we
have

$\mathop{{\operatorname{{Pr}}}\/}_{{\bm{T}}_{1},\ldots,{\bm{T}}_{r}\sim\tau}\bigg{[}\text{MAJ}({\bm{T}}_{1}(x),\ldots,{\bm{T}}_{r}(x))\neq
f(x)\bigg{]}\leq 2^{-\Omega(\gamma^{2}r)}$

by a Chernoff bound. Choosing $r=\Theta(\log(1/\delta)/\gamma^{2})$ ensures
that the failure probability is at most $\delta/2$. The decision tree
${\bm{T}}^{\star}$ satisfies
$\operatorname{{Pr}}_{\bm{x}\sim\mu}[{\bm{T}}^{\star}(\bm{x})\neq
f(\bm{x})]\leq\delta$. The expected depth of ${\bm{T}}^{\star}$ is less than

$r\cdot
d=\Theta(d\log(1/\delta)/\gamma^{2})<\overline{\mathrm{Depth}}^{\mu}(f,\delta)$

which is a contradiction.

##  Appendix C The lack of error reduction for distributional error

In Section 2, we showed how error reduction gave a simple proof of a strong
direct sum theorem for _randomized_ query complexity. The specific statement
needed in that proof is the following standard error reduction by repetition
theorem.

######  Fact C.1 (Error reduction for $\overline{\mathrm{R}}$).

For any function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ and $\delta>0$,

$\overline{\mathrm{R}}(f,\delta)\leq
O(\log(\textstyle\frac{1}{\delta}))\cdot\overline{\mathrm{R}}(f,1/4).$

Here, we give a short proof that no error reduction holds in the
distributional setting, even with substantially weaker parameters.

######  Claim C.2.

For any $n\in\mathds{N}$, let $\mu$ be the uniform distribution over $\\{\pm
1\\}^{n}$. There is a function $f:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ satisfying,

$\overline{\mathrm{Depth}}^{\mu}(f,1/4)=0\quad\quad\quad\text{and}\quad\quad\quad\overline{\mathrm{Depth}}^{\mu}(f,1/8)\geq\Omega(n).$

Since any function on $n$ bits can be computed exactly using $n$, the $f$ in
the above claim requires essentially the maximum number of queries to be
computed to error $1/8$ despite requiring no queries to be computed to error
$1/4$.

###### Proof.

We first define $f$: If $x_{1}=0$, then $f(x)=0$. Otherwise, $f(x)$ is the
parity of the remaining $n-1$ bits of $x$.

Note that,

$\operatorname{{Pr}}_{\bm{x}\sim\mu}[f(\bm{x})=0]=\frac{1}{2}\cdot\left(\operatorname{{Pr}}[f(\bm{x})=0\mid\bm{x}_{1}=0]+\operatorname{{Pr}}[f(\bm{x})=0\mid\bm{x}_{1}=1]\right)=\frac{3}{4}.$

Therefore, the $0$ query algorithm that simply outputs $0$ has an error of
only $1/4$ on $f$.

It only remains to prove that
$\overline{\mathrm{Depth}}^{\mu}(f,1/10)\geq\Omega(n)$. Consider any
(potentially randomized) $T:\\{\pm 1\\}^{n}\to\\{\pm 1\\}$ and leaf $\ell$ of
$T$ at depth strictly less than $n-1$. By Proposition 10.2

$\operatorname{{Pr}}_{\bm{x}\sim\mu}[T(\bm{x})\neq f(\bm{x})\mid\bm{x}\text{
reaches }\ell,\bm{x}_{1}=1]=1/2.$

Let $p$ be the probability that $T(\bm{x})$ queries a leaf of depth at least
$n-1$ given that $\bm{x}_{1}=1$. The above allows us to conclude that

$\operatorname{{Pr}}_{\bm{x}\sim\mu}[T(\bm{x})\neq
f(\bm{x})]\geq\frac{1}{2}\cdot\operatorname{{Pr}}[T(\bm{x})\neq
f(\bm{x})\mid\bm{x}_{1}=1]\geq\frac{1}{4}\cdot p.$

Therefore, if $T$ has error at most $1/8$, then $p$ must be at least $1/2$,
which shows that $\overline{\mathrm{Depth}}^{\mu}(f,1/8)\geq\frac{n-1}{4}$. ∎