- Distinguishing Two Probability Ensembles with One Sample from each Ensemble
- Theory of Computing Systems
- Volume | Issue number
- 59 | 3
- Pages (from-to)
- Number of pages
- Document type
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
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.
- go to publisher's site
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.