All reports by Author Aryeh Grinberg:

__
TR18-061
| 6th April 2018
__

Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola#### Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs

Revisions: 5

Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola

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