We study how well can $q$-query decision trees distinguish between the
following two distributions: (i) $R=(R_1,\ldots,R_N)$ that are i.i.d.
variables, (ii) $X=(R|R \in A)$ where $A$ is an event s.t. $\Pr[R \in A] \ge
2^{-a}$. We prove two lemmas:

- Forbidden-set lemma: There exists $B \subseteq [N]$ of
size $poly(a,q,\frac{1}{\eta})$ such that $q$-query trees that do not
query variables in $B$ cannot distinguish $X$ from $R$ with
advantage $\eta$.

- Fixed-set lemma: There exists $B \subseteq [N]$ of size
$poly(a,q,\frac{1}{\eta})$ and $v\in \B^B$ such that $q$-query trees
do not distinguish $(X|X_B=v)$ from $(R|R_B=v)$ with advantage
$\eta$.

The first can be seen as an extension of past work by Edmonds,
Impagliazzo, Rudich and Sgall (Computational Complexity 2001), Raz
(SICOMP 1998), and Shaltiel and Viola (SICOMP 2010) to adaptive
decision trees. We can also derive it from recent, independent work by
Meir and Wigderson (ECCC 2017) who use different techniques.

We use the second, fixed-set lemma to prove lower bounds on black-box
proofs for hardness amplification that amplify hardness from $\delta$ to
$1/2-\epsilon$. Specifically:

- Reductions must make $q=\Omega(\log(1/\delta)/\epsilon^2)$
queries, implying a ``size loss factor'' of $q$. We also prove the
lower bound $q=\Omega(\log(1/\delta)/\epsilon)$ for ``error-less''
hardness amplification proofs, and for direct-product lemmas. These
bounds are tight.

- Reductions can be used to compute Majority on
$\Omega(1/\epsilon)$ bits, implying that black box proofs cannot amplify
hardness of functions that are hard against constant depth circuits
(unless they are allowed to use Majority gates).

Both items extend to pseudorandom-generator constructions.

These results prove conjectures in Viola's Ph.D.~Thesis (2006), and
improve on three incomparable previous works (Shaltiel and Viola,
SICOMP 2010; Gutfreund and Rothblum, RANDOM 2008; Artemenko and
Shaltiel, Computational Complexity 2014).

We study how well can $q$-query decision trees distinguish between the
following two distributions: (i) $R=(R_1,\ldots,R_N)$ that are i.i.d.
variables, (ii) $X=(R|R \in A)$ where $A$ is an event s.t. $\Pr[R \in A] \ge
2^{-a}$. We prove two lemmas:

- Forbidden-set lemma: There exists $B \subseteq [N]$ of
size $poly(a,q,\frac{1}{\eta})$ such that $q$-query trees that do not
query variables in $B$ cannot distinguish $X$ from $R$ with
advantage $\eta$.

- Fixed-set lemma: There exists $B \subseteq [N]$ of size
$poly(a,q,\frac{1}{\eta})$ and $v\in \B^B$ such that $q$-query trees
do not distinguish $(X|X_B=v)$ from $(R|R_B=v)$ with advantage
$\eta$.

The first can be seen as an extension of past work by Edmonds,
Impagliazzo, Rudich and Sgall (Computational Complexity 2001), Raz
(SICOMP 1998), and Shaltiel and Viola (SICOMP 2010) to adaptive
decision trees. We can also derive it from recent, independent work by
Meir and Wigderson (ECCC 2017) who use different techniques.

We use the second, fixed-set lemma to prove lower bounds on black-box
proofs for hardness amplification that amplify hardness from $\delta$ to
$1/2-\epsilon$. Specifically:

- Reductions must make $q=\Omega(\log(1/\delta)/\epsilon^2)$
queries, implying a ``size loss factor'' of $q$. We also prove the
lower bound $q=\Omega(\log(1/\delta)/\epsilon)$ for ``error-less''
hardness amplification proofs, and for direct-product lemmas. These
bounds are tight.

- Reductions can be used to compute Majority on
$\Omega(1/\epsilon)$ bits, implying that black box proofs cannot amplify
hardness of functions that are hard against constant depth circuits
(unless they are allowed to use Majority gates).

Both items extend to pseudorandom-generator constructions.

These results prove conjectures in Viola's Ph.D.~Thesis (2006), and
improve on three incomparable previous works (Shaltiel and Viola,
SICOMP 2010; Gutfreund and Rothblum, RANDOM 2008; Artemenko and
Shaltiel, Computational Complexity 2014).

Rewritten Section 5.2.

We study how well can $q$-query decision trees distinguish between the
following two distributions: (i) $R=(R_1,\ldots,R_N)$ that are i.i.d.
variables, (ii) $X=(R|R \in A)$ where $A$ is an event s.t. $\Pr[R \in A] \ge
2^{-a}$. We prove two lemmas:

- Forbidden-set lemma: There exists $B \subseteq [N]$ of
size $poly(a,q,\frac{1}{\eta})$ such that $q$-query trees that do not
query variables in $B$ cannot distinguish $X$ from $R$ with
advantage $\eta$.

- Fixed-set lemma: There exists $B \subseteq [N]$ of size
$poly(a,q,\frac{1}{\eta})$ and $v\in \B^B$ such that $q$-query trees
do not distinguish $(X|X_B=v)$ from $(R|R_B=v)$ with advantage
$\eta$.

The first can be seen as an extension of past work by Edmonds,
Impagliazzo, Rudich and Sgall (Computational Complexity 2001), Raz
(SICOMP 1998), and Shaltiel and Viola (SICOMP 2010) to
\emph{adaptive} decision trees. It is independent of recent work by Meir
and Wigderson (ECCC 2017) bounding the number of $i \in [N]$ for which
there exists a $q$-query tree that predicts $X_i$ from the other bits.

We use the second, fixed-set lemma to prove lower bounds on black-box
proofs for hardness amplification that amplify hardness from $\delta$ to
$1/2-\epsilon$. Specifically:

- Reductions must make $q=\Omega(\log(1/\delta)/\epsilon^2)$
queries, implying a ``size loss factor'' of $q$. We also prove the
lower bound $q=\Omega(\log(1/\delta)/\epsilon)$ for ``error-less''
hardness amplification proofs, and for direct-product lemmas. These
bounds are tight.

- Reductions can be used to compute Majority on
$\Omega(1/\epsilon)$ bits, implying that black box proofs cannot amplify
hardness of functions that are hard against constant depth circuits
(unless they are allowed to use Majority gates).

Both items extend to pseudorandom-generator constructions.

These results prove 15-year-old conjectures by Viola, and improve on
three incomparable previous works (Shaltiel and Viola, SICOMP 2010;
Gutfreund and Rothblum, RANDOM 2008; Artemenko and Shaltiel,
Computational Complexity 2014).

Relationship to work by Meir and Wigderson, and other minor corrections.

We study how well can $q$-query decision trees distinguish between the
following two distributions: (i) $R=(R_1,\ldots,R_N)$ that are i.i.d.
variables, (ii) $X=(R|R \in A)$ where $A$ is an event s.t. $\Pr[R \in A] \ge
2^{-a}$. We prove two lemmas:

- Forbidden-set lemma: There exists $B \subseteq [N]$ of
size $poly(a,q,\frac{1}{\eta})$ such that $q$-query trees that do not
query variables in $B$ cannot distinguish $X$ from $R$ with
advantage $\eta$.

- Fixed-set lemma: There exists $B \subseteq [N]$ of size
$poly(a,q,\frac{1}{\eta})$ and $v\in \B^B$ such that $q$-query trees
do not distinguish $(X|X_B=v)$ from $(R|R_B=v)$ with advantage
$\eta$.

The first can be seen as an extension of past work by Edmonds,
Impagliazzo, Rudich and Sgall (Computational Complexity 2001), Raz
(SICOMP 1998), and Shaltiel and Viola (SICOMP 2010) to adaptive
decision trees. We can also derive it from recent, independent work by
Meir and Wigderson (ECCC 2017) who use different techniques.

We use the second, fixed-set lemma to prove lower bounds on black-box
proofs for hardness amplification that amplify hardness from $\delta$ to
$1/2-\epsilon$. Specifically:

- Reductions must make $q=\Omega(\log(1/\delta)/\epsilon^2)$
queries, implying a ``size loss factor'' of $q$. We also prove the
lower bound $q=\Omega(\log(1/\delta)/\epsilon)$ for ``error-less''
hardness amplification proofs, and for direct-product lemmas. These
bounds are tight.

- Reductions can be used to compute Majority on
$\Omega(1/\epsilon)$ bits, implying that black box proofs cannot amplify
hardness of functions that are hard against constant depth circuits
(unless they are allowed to use Majority gates).

Both items extend to pseudorandom-generator constructions.

These results prove conjectures in Viola's Ph.D.~Thesis (2006), and
improve on three incomparable previous works (Shaltiel and Viola,
SICOMP 2010; Gutfreund and Rothblum, RANDOM 2008; Artemenko and
Shaltiel, Computational Complexity 2014).

Remark 1.5.

We study how well can $q$-query decision trees distinguish between the
following two distributions: (i) $R=(R_1,\ldots,R_N)$ that are i.i.d.
variables, (ii) $X=(R|R \in A)$ where $A$ is an event s.t. $\Pr[R \in A] \ge
2^{-a}$. We prove two lemmas:

- Forbidden-set lemma: There exists $B \subseteq [N]$ of
size $poly(a,q,\frac{1}{\eta})$ such that $q$-query trees that do not
query variables in $B$ cannot distinguish $X$ from $R$ with
advantage $\eta$.

- Fixed-set lemma: There exists $B \subseteq [N]$ of size
$poly(a,q,\frac{1}{\eta})$ and $v\in \B^B$ such that $q$-query trees
do not distinguish $(X|X_B=v)$ from $(R|R_B=v)$ with advantage
$\eta$.

The first can be seen as an extension of past work by Edmonds,
Impagliazzo, Rudich and Sgall (Computational Complexity 2001), Raz
(SICOMP 1998), and Shaltiel and Viola (SICOMP 2010) to adaptive
decision trees. We can also derive it from recent, independent work by
Meir and Wigderson (ECCC 2017) who use different techniques.

We use the second, fixed-set lemma to prove lower bounds on black-box
proofs for hardness amplification that amplify hardness from $\delta$ to
$1/2-\epsilon$. Specifically:

- Reductions must make $q=\Omega(\log(1/\delta)/\epsilon^2)$
queries, implying a ``size loss factor'' of $q$. We also prove the
lower bound $q=\Omega(\log(1/\delta)/\epsilon)$ for ``error-less''
hardness amplification proofs, and for direct-product lemmas. These
bounds are tight.

- Reductions can be used to compute Majority on
$\Omega(1/\epsilon)$ bits, implying that black box proofs cannot amplify
hardness of functions that are hard against constant depth circuits
(unless they are allowed to use Majority gates).

Both items extend to pseudorandom-generator constructions.

These results prove conjectures in Viola's Ph.D.~Thesis (2006), and
improve on three incomparable previous works (Shaltiel and Viola,
SICOMP 2010; Gutfreund and Rothblum, RANDOM 2008; Artemenko and
Shaltiel, Computational Complexity 2014).

Only change is the addition of an acknowledgement.

We study how well can $q$-query decision trees distinguish between the
following two distributions: (i) $R=(R_1,\ldots,R_N)$ that are i.i.d.
variables, (ii) $X=(R|R \in A)$ where $A$ is an event s.t. $\Pr[R \in A] \ge
2^{-a}$. We prove two lemmas:

- Forbidden-set lemma: There exists $B \subseteq [N]$ of
size $poly(a,q,\frac{1}{\eta})$ such that $q$-query trees that do not
query variables in $B$ cannot distinguish $X$ from $R$ with
advantage $\eta$.

- Fixed-set lemma: There exists $B \subseteq [N]$ of size
$poly(a,q,\frac{1}{\eta})$ and $v\in \B^B$ such that $q$-query trees
do not distinguish $(X|X_B=v)$ from $(R|R_B=v)$ with advantage
$\eta$.

The first can be seen as an extension of past work by Edmonds,
Impagliazzo, Rudich and Sgall (Computational Complexity 2001), Raz
(SICOMP 1998), and Shaltiel and Viola (SICOMP 2010) to adaptive
decision trees. We can also derive it from recent, independent work by
Meir and Wigderson (ECCC 2017) who use different techniques.

We use the second, fixed-set lemma to prove lower bounds on black-box
proofs for hardness amplification that amplify hardness from $\delta$ to
$1/2-\epsilon$. Specifically:

- Reductions must make $q=\Omega(\log(1/\delta)/\epsilon^2)$
queries, implying a ``size loss factor'' of $q$. We also prove the
lower bound $q=\Omega(\log(1/\delta)/\epsilon)$ for ``error-less''
hardness amplification proofs, and for direct-product lemmas. These
bounds are tight.

- Reductions can be used to compute Majority on
$\Omega(1/\epsilon)$ bits, implying that black box proofs cannot amplify
hardness of functions that are hard against constant depth circuits
(unless they are allowed to use Majority gates).

Both items extend to pseudorandom-generator constructions.

These results prove conjectures in Viola's Ph.D.~Thesis (2006), and
improve on three incomparable previous works (Shaltiel and Viola,
SICOMP 2010; Gutfreund and Rothblum, RANDOM 2008; Artemenko and
Shaltiel, Computational Complexity 2014).