ECCC-Report TR18-061https://eccc.weizmann.ac.il/report/2018/061Comments and Revisions published for TR18-061en-usSun, 05 Aug 2018 17:44:21 +0300
Revision 5
| Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs |
Aryeh Grinberg,
Ronen Shaltiel,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2018/061#revision5We 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).
Sun, 05 Aug 2018 17:44:21 +0300https://eccc.weizmann.ac.il/report/2018/061#revision5
Revision 4
| Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs |
Aryeh Grinberg,
Ronen Shaltiel,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2018/061#revision4We 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).
Sun, 06 May 2018 15:52:17 +0300https://eccc.weizmann.ac.il/report/2018/061#revision4
Revision 3
| Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs |
Aryeh Grinberg,
Ronen Shaltiel,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2018/061#revision3We 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).
Thu, 03 May 2018 20:37:30 +0300https://eccc.weizmann.ac.il/report/2018/061#revision3
Revision 2
| Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs |
Aryeh Grinberg,
Ronen Shaltiel,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2018/061#revision2We 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).
Tue, 10 Apr 2018 15:50:19 +0300https://eccc.weizmann.ac.il/report/2018/061#revision2
Revision 1
| Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs |
Aryeh Grinberg,
Ronen Shaltiel,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2018/061#revision1We 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).
Sun, 08 Apr 2018 15:46:16 +0300https://eccc.weizmann.ac.il/report/2018/061#revision1
Paper TR18-061
| Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs |
Aryeh Grinberg,
Ronen Shaltiel,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2018/061We 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).
Fri, 06 Apr 2018 16:59:50 +0300https://eccc.weizmann.ac.il/report/2018/061