Computational indistinguishability: A sample hierarchy

zbMATH Open0947.68066MaRDI QIDQ1961376FDOQ1961376

Authors: Oded Goldreich, Madhu Sudan 

Publication date: 17 January 2000

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

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

zbMATH Keywords

eigenvaluespolynomialsexpandersextractorsrapid mixingcomputational indistinguishability

Mathematics Subject Classification ID

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

Cites Work

• Probabilistic encryption
• The eigenvalues of random symmetric matrices
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Title not available (Why is that?)
• Title not available (Why is that?)
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• Title not available (Why is that?)
• Computational indistinguishability: algorithms vs. circuits

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\)
• Title not available (Why is that?)
• 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)