Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #5 to TR18-061 | 5th August 2018 17:44

Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs

RSS-Feed




Revision #5
Authors: Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola
Accepted on: 5th August 2018 17:44
Downloads: 39
Keywords: 


Abstract:

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 to TR18-061 | 6th May 2018 15:52

Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs





Revision #4
Authors: Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola
Accepted on: 6th May 2018 15:52
Downloads: 48
Keywords: 


Abstract:

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



Changes to previous version:

Rewritten Section 5.2.


Revision #3 to TR18-061 | 3rd May 2018 20:37

Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs





Revision #3
Authors: Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola
Accepted on: 3rd May 2018 20:37
Downloads: 40
Keywords: 


Abstract:

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



Changes to previous version:

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


Revision #2 to TR18-061 | 10th April 2018 15:50

Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs





Revision #2
Authors: Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola
Accepted on: 10th April 2018 15:50
Downloads: 66
Keywords: 


Abstract:

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



Changes to previous version:

Remark 1.5.


Revision #1 to TR18-061 | 8th April 2018 15:46

Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs





Revision #1
Authors: Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola
Accepted on: 8th April 2018 15:46
Downloads: 53
Keywords: 


Abstract:

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



Changes to previous version:

Only change is the addition of an acknowledgement.


Paper:

TR18-061 | 6th April 2018 16:59

Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs





TR18-061
Authors: Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola
Publication: 6th April 2018 16:59
Downloads: 139
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint