search Select option IT People Sci. activity Ac. activity Oportunities News Links
 Scientific Areas
 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)