From absolute distinguishability to positive distinguishability
Webpage for a paper by Zvika Brakerski and Oded Goldreich
Abstract
We study methods of converting algorithms that distinguish pairs
of distributions with a gap that has an absolute value that is noticeable
into corresponding algorithms in which the gap is always positive.
Our focus is on designing algorithms that, in addition to the tested string,
obtain a fixed number of samples from each distribution.
Needless to say, such algorithms can not provide a very reliable
guess for the sign of the original distinguishability gap,
still we show that even guesses that are noticeably better than random
are useful in this setting.
Material available on-line
Back to
either Oded Goldreich's homepage.
or general list of papers.