Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > RON D. ROTHBLUM:
All reports by Author Ron D. Rothblum:

TR19-038 | 7th March 2019
Itay Berman, Akshay Degwekar, Ron D. Rothblum, Prashant Vasudevan

Statistical Difference Beyond the Polarizing Regime

Revisions: 1

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




ISSN 1433-8092 | Imprint