Distinguishing Two Probability Ensembles with One Sample from each Ensemble

• Tipo: Artigo em Revista Científica Internacional
• Data: 2016

Autores

antunes, l (Autor) FCUP; Buhrman, H (Autor) Outra; Matos, A (Autor) Outra; souto, a (Autor) Outra; teixeira, a (Autor) Outra

Revista

Título: Theory of Computing Systems

Vol. 59

Páginas: 517-531

ISSN: 1432-4350

Editora: Springer Nature

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 0 Citações

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 15