Distinguishing probability ensembles
- A. Matos; A. T. Teixeira; Souto, A.;
"Distinguishing probability ensembles
", Proc
Computability in Europe - CIE
,
Sofia
,
Bulgaria
, Vol.
n/a
, pp.
155
-
164
,
June
,
2011
.
Abstract
We generalize the concept of distinguishability, based on the input
or the output of the randomized, polynomial-time distinguishing
algorithms. First we consider algorithms with an arbitrary integer
output (instead of just~0 or~1) and prove that, when the output is
bounded by a polynomial, these distinguishers are no more powerful than
a variant of the classical (computational) ones in which the
algorithms may have a short advice (order~$O(\log n)$).
%\mbar{-27.5}{29}
Then, we characterize a distinguishing method in which two samples,
one from {\em each} ensemble, may be given as input to the algorithm (the
case of two or more samples of the {\em same} ensemble as input has
already been studied in~\cite{GM98,GS98}) and we study the properties
of this new distinguishing method. Finally, we use, as
distinguishers, algorithms that are lossless compressors and output
the {\em length} of the compressed string; somewhat surprisingly,
any pair of classically distinguishable ensembles, is also
distinguishable by the length of the output of some compressor.
Full text (PDF 281KB)
