Computational indistinguishability: A sample hierarchy

MaRDI QIDQ1961376zbMATH OpenFDO

Authors Oded Goldreich, Madhu Sudan

Publication date 17 January 2000

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

eigenvaluespolynomialsexpandersextractorsrapid mixingcomputational indistinguishability

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1335877
• The Complexity of Distinguishing Distributions (Invited Talk)
• Computational indistinguishability: algorithms vs. circuits
• scientific article; zbMATH DE number 1301087
• On the randomness complexity of efficient sampling

Cites work

• scientific article; zbMATH DE number 3960854 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1097580 (Why is no real title available?)
• Computational indistinguishability: algorithms vs. circuits
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• Probabilistic encryption
• The eigenvalues of random symmetric matrices

Cited in

(7)

• Sublinear bounds on the distinguishing advantage for multiple samples
• \texttt{Sample(x)=(a*x<=t)} is a distinguisher with probability \(1/8\)
• scientific article; zbMATH DE number 1301087 (Why is no real title available?)
• Outcome indistinguishability
• A note on computational indistinguishability
• Distinguishing two probability ensembles with one sample from each ensemble
• From absolute distinguishability to positive distinguishability

This page was built for publication: Computational indistinguishability: A sample hierarchy

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