Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR09-031 | 6th April 2009 00:00

From absolute distinguishability to positive distinguishability

RSS-Feed




TR09-031
Authors: Zvika Brakerski, Oded Goldreich
Publication: 6th April 2009 11:18
Downloads: 2193
Keywords: 


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.



ISSN 1433-8092 | Imprint