Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > POLARIZATION LEMMA:
Reports tagged with Polarization Lemma:
TR16-140 | 9th September 2016
Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan

#### On SZK and PP

Revisions: 3

In both query and communication complexity, we give separations between the class NISZK, containing those problems with non-interactive statistical zero knowledge proof systems, and the class UPP, containing those problems with randomized algorithms with unbounded error. These results significantly improve on earlier query separations of Vereschagin [Ver95] and Aaronson [Aar12] ... more >>>

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