ECCC-Report TR19-038https://eccc.weizmann.ac.il/report/2019/038Comments and Revisions published for TR19-038en-usTue, 14 May 2019 22:27:32 +0300
Revision 1
| Statistical Difference Beyond the Polarizing Regime |
Itay Berman,
Akshay Degwekar,
Ron D. Rothblum,
Prashant Nalini Vasudevan
https://eccc.weizmann.ac.il/report/2019/038#revision1The polarization lemma for statistical distance ($\mathrm{SD}$), due to Sahai and Vadhan (JACM, 2003), is an efficient transformation taking as input a pair of circuits $(C_0,C_1)$ and an integer $k$ and outputting a new pair of circuits $(D_0,D_1)$ such that if $\mathrm{SD}(C_0,C_1) \geq \alpha$ then $\mathrm{SD}(D_0,D_1) \geq 1-2^{-k}$ and if $\mathrm{SD}(C_0,C_1) \leq \beta$ then $\mathrm{SD}(D_0,D_1) \leq 2^{-k}$. The polarization lemma is known to hold for any constant values $\beta < \alpha^2$, but extending the lemma to the regime in which $\alpha^2 \leq \beta < \alpha$ has remained elusive. The focus of this work is in studying the latter regime of parameters. Our main results are:
1. Polarization lemmas for different notions of distance, such as Triangular Discrimination ($\mathrm{TD}$) and Jensen-Shannon Divergence ($\mathrm{JS}$), which enable polarization for some problems where the statistical distance
satisfies $ \alpha^2 < \beta < \alpha$. We also derive a polarization lemma for statistical distance with any inverse-polynomially small gap between $\alpha^2$ and $\beta$ (rather than a constant).
2. The average-case hardness of the statistical difference problem (i.e., determining whether the statistical distance between two given circuits is at least $\alpha$ or at most $\beta$), for any values of $\beta < \alpha$, implies the existence of one-way functions. Such a result was previously only known for
$\beta < \alpha^2$.
3. A (direct) constant-round interactive proof for estimating the statistical distance between any two distributions (up to any inverse polynomial error) given circuits that generate them. Proofs of closely related statements have
appeared in the literature but we give a new proof which we find to be cleaner and more direct.Tue, 14 May 2019 22:27:32 +0300https://eccc.weizmann.ac.il/report/2019/038#revision1
Paper TR19-038
| Statistical Difference Beyond the Polarizing Regime |
Itay Berman,
Akshay Degwekar,
Ron D. Rothblum,
Prashant Vasudevan
https://eccc.weizmann.ac.il/report/2019/038The polarization lemma for statistical distance ($\mathrm{SD}$), due to Sahai and Vadhan (JACM, 2003), is an efficient transformation taking as input a pair of circuits $(C_0,C_1)$ and an integer $k$ and outputting a new pair of circuits $(D_0,D_1)$ such that if $\mathrm{SD}(C_0,C_1)\geq\alpha$ then $\mathrm{SD}(D_0,D_1) \geq 1-2^{-k}$ and if $\mathrm{SD}(C_0,C_1) \leq \beta$ then $\mathrm{SD}(D_0,D_1) \leq 2^{-k}$. The polarization lemma is known to hold for any constant values $\beta < \alpha^2$, but extending the lemma to the regime in which $\alpha^2 \leq \beta < \alpha$ has remained elusive. The focus of this work is in studying the latter regime of parameters. Our main results are:
1. Polarization lemmas for different notions of distance, such as Triangular Discrimination ($\mathrm{TD}$) and Jensen-Shannon Divergence ($\mathrm{JS}$), which enable polarization for some problems where the statistical distance satisfies $\alpha^2 < \beta < \alpha$. We also derive a polarization lemma for statistical distance with any inverse-polynomially small gap between $\alpha^2$ and $\beta$ (rather than a constant).
2. The average-case hardness of the statistical difference problem (i.e., determining whether the statistical distance between two given circuits is at least $\alpha$ or at most $\beta$), for any values of $\beta < \alpha$, implies the existence of one-way functions. Such a result was previously only known for $\beta < \alpha^2$.
3. A (direct) constant-round interactive proof for estimating the statistical distance between any two distributions (up to any inverse polynomial error) given circuits that generate them.Sun, 10 Mar 2019 10:50:14 +0200https://eccc.weizmann.ac.il/report/2019/038