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

Accepted on: 10th April 2018 15:50

Downloads: 26

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

Remark 1.5.

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

Accepted on: 8th April 2018 15:46

Downloads: 16

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

Only change is the addition of an acknowledgement.

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

Publication: 6th April 2018 16:59

Downloads: 96

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