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 ]