Manipulating Statistical Difference

Amit Sahai and Salil Vadhan

Abstract

We give several efficient transformations for manipulating the statistical difference (variation distance) between a pair of probability distributions. The effects achieved include increasing the statistical difference, decreasing the statistical difference, "polarizing" the statistical relationship, and "reversing" the statistical relationship. We also show that a boolean formula whose atoms are statements about statistical difference can be transformed into a single statement about statistical difference. All of these transformations can be performed in polynomial time, in the sense that, given circuits which sample from the input distributions, it only takes polynomial time to compute circuits which sample from the output distributions.

By our prior work (see FOCS 97), such transformations for manipulating statistical difference are closely connected to results about SZK, the class of languages possessing statistical zero-knowledge proofs. In particular, some of the transformations given in this paper are equivalent to the closure of SZK under complement and under certain types of Turing reductions. This connection is also discussed briefly in this paper.

Versions

BibTeX entry

@InProceedings{SahaiVa99,
  author =       {Amit Sahai and Salil Vadhan},
  title =        {Manipulating Statistical Difference},
  booktitle =    {Randomization Methods in Algorithm Design ({DIMACS} Workshop, December 1997)},
  editor =       {Panos Pardalos and Sanguthevar Rajasekaran and Jos{\'e} Rolim},
  volume =       {43},
  series =       {{DIMACS} Series in Discrete Mathematics and Theoretical Computer Science},
  year =         {1999},
  publisher =    {American Mathematical Society},
  pages =        {251--270},
}
 [ back to Salil Vadhan's research interests ]