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.