Revision #5 Authors: Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola

Accepted on: 5th August 2018 17:44

Downloads: 17

Keywords:

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

Revision #4 Authors: Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola

Accepted on: 6th May 2018 15:52

Downloads: 39

Keywords:

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.

Revision #3 Authors: Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola

Accepted on: 3rd May 2018 20:37

Downloads: 34

Keywords:

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.

Revision #2 Authors: Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola

Accepted on: 10th April 2018 15:50

Downloads: 54

Keywords:

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:

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

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

proofs for hardness amplification that amplify hardness from $\delta$ to

$1/2-\epsilon$. Specifically:

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.

$\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.

Revision #1 Authors: Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola

Accepted on: 8th April 2018 15:46

Downloads: 48

Keywords:

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:

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

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

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.

proofs for hardness amplification that amplify hardness from $\delta$ to

$1/2-\epsilon$. Specifically:

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.

$\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.

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.

TR18-061 Authors: Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola

Publication: 6th April 2018 16:59

Downloads: 127

Keywords:

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:

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

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

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.

proofs for hardness amplification that amplify hardness from $\delta$ to

$1/2-\epsilon$. Specifically:

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.

$\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.

improve on three incomparable previous works (Shaltiel and Viola,

SICOMP 2010; Gutfreund and Rothblum, RANDOM 2008; Artemenko and

Shaltiel, Computational Complexity 2014).