Distinguishing two probability ensembles with one sample from each ensemble

DOI10.1007/S00224-015-9661-1MaRDI QIDQ503466zbMATH OpenOpenAlexWikidataFDO

Authors Luís Antunes, Harry Buhrman, André Souto, Armando B. Matos, Andreia Sofia Teixeira

Publication date 12 January 2017

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL http://repositorio.inesctec.pt/handle/123456789/7057

zbMATH Keywords

communication complexityindistinguishabilitymulti-sample distinguisherssingle-message protocols

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Cryptography (94A60)

Recommendations

• Computational indistinguishability: A sample hierarchy
• scientific article; zbMATH DE number 1335877
• Testing Symmetric Properties of Distributions
• Computational indistinguishability: algorithms vs. circuits
• The Complexity of Distinguishing Distributions (Invited Talk)

Cites work

• A Hardcore Lemma for Computational Indistinguishability: Security Amplification for Arbitrarily Weak PRGs with Optimal Stretch
• Communication Complexity
• Communication complexity in a 3-computer model
• Computational indistinguishability: A sample hierarchy
• Computational indistinguishability: algorithms vs. circuits
• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256775 (Why is no real title available?)
• scientific article; zbMATH DE number 1769898 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)

Cited in

(3)

• From absolute distinguishability to positive distinguishability
• scientific article; zbMATH DE number 1335877 (Why is no real title available?)
• \texttt{Sample(x)=(a*x<=t)} is a distinguisher with probability \(1/8\)

This page was built for publication: Distinguishing two probability ensembles with one sample from each ensemble

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q503466)