Distinguishing Two Probability Ensembles with One Sample from each Ensemble

• Type: Article in International Scientific Journal
• Date: 2016

Authors

antunes, l (Author) FCUP; Buhrman, H (Author) Other; Matos, A (Author) Other; souto, a (Author) Other; teixeira, a (Author) Other

Journal

Title: Theory of Computing Systems

Vol. 59

Pages: 517-531

ISSN: 1432-4350

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 0 Citations

Scopus - 0 Citations

Other information

Authenticus ID: P-00G-SFS

DOI: 10.1007/s00224-015-9661-1

Abstract (EN): We introduced a new method for distinguishing two probability ensembles called one from each method, in which the distinguisher receives as input two samples, one from each ensemble. We compare this new method with multi-sample from the same method already exiting in the literature and prove that there are ensembles distinguishable by the new method, but indistinguishable by the multi-sample from the same method. To evaluate the power of the proposed method we also show that if non-uniform distinguishers (probabilistic circuits) are used, the one from each method is not more powerful than the classical one, in the sense that does not distinguish more probability ensembles. Moreover we obtain that there are classes of ensembles, such that any two members of the class are easily distinguishable (a definition introduced in this paper) using one sample from each ensemble; there are pairs of ensembles in the same class that are indistinguishable by multi-sample from the same method.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 15