Randomness and computation

DOI10.1007/978-3-642-22670-0_33MaRDI QIDQ3088199zbMATH OpenOpenAlexFDO

Authors Oded Goldreich

Publication date 19 August 2011

Published in Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22670-0_33

zbMATH Keywords

pseudorandomnessproperty testingzero-knowledge proofsprobabilistically checkable proofsencryption schemesinteractive proofsmessage authentication schemes

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Cryptography (94A60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Randomness -- a computational complexity perspective
• Randomness, computation and mathematics
• Modern cryptography, probabilistic proofs and pseudo-randomness
• Randomization, persuasiveness and rigor in proofs
• Randomness – A Computational Complexity Perspective

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3960854 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A Brief Introduction to Property Testing
• A Pseudorandom Generator from any One-way Function
• Algebraic methods for interactive proof systems
• Algorithmic and analysis techniques in property testing
• Approximation algorithms for NP-hard problems.
• Computational Complexity
• Foundations of Cryptography
• Foundations of Cryptography
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• IP = PSPACE
• Interactive proofs and the hardness of approximating cliques
• Introduction to testing graph properties
• P, NP, and NP-completeness. The basics of computational complexity.
• Probabilistic checking of proofs
• Probabilistic encryption
• Proof verification and the hardness of approximation problems
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• The Knowledge Complexity of Interactive Proof Systems

Cited in

(15)

• scientific article; zbMATH DE number 1195809 (Why is no real title available?)
• On randomized versus deterministic computation
• Randomness -- a computational complexity perspective
• scientific article; zbMATH DE number 1688364 (Why is no real title available?)
• scientific article; zbMATH DE number 969633 (Why is no real title available?)
• Cryptographic assumptions: a position paper
• Randomness – A Computational Complexity Perspective
• The Power and Weakness of Randomness in Computation
• Randomness, pseudorandomness and models of arithmetic
• Randomness, arrays, differences and duality
• scientific article; zbMATH DE number 6019540 (Why is no real title available?)
• scientific article; zbMATH DE number 1834658 (Why is no real title available?)
• scientific article; zbMATH DE number 5057386 (Why is no real title available?)
• Computing with Very Weak Random Sources
• Random numbers as probabilities of machine behavior

This page was built for publication: Randomness and computation

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