Randomness – A Computational Complexity Perspective

DOI10.1007/978-3-540-79709-8_1MaRDI QIDQ3503618zbMATH OpenOpenAlexFDO

Authors A. Wigderson

Publication date 5 June 2008

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-79709-8_1

zbMATH Keywords

complexityderandomnizationpseudorandomrandomness

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Randomness -- a computational complexity perspective
• scientific article; zbMATH DE number 7377983
• Randomness and computation
• Randomness and completeness in computational complexity
• scientific article; zbMATH DE number 1531917
• scientific article; zbMATH DE number 969633
• Algorithmic randomness and measures of complexity
• Complexity and randomness
• Computability, algorithmic randomness and complexity
• The Power and Weakness of Randomness in Computation

Cites work

• \({\mathcal P}\), \({\mathcal{NP}}\) and mathematics -- a computational complexity perspective
• scientific article; zbMATH DE number 1820017 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)

Cited in

(11)

• Modern cryptography, probabilistic proofs and pseudo-randomness
• On randomized versus deterministic computation
• scientific article; zbMATH DE number 1688364 (Why is no real title available?)
• Pseudorandomness
• Randomness -- a computational complexity perspective
• Randomness and computation
• scientific article; zbMATH DE number 6019540 (Why is no real title available?)
• A relation between correctness and randomness in the computation of probabilistic algorithms
• Pairwise independence and derandomization.
• scientific article; zbMATH DE number 1857655 (Why is no real title available?)
• scientific article; zbMATH DE number 969633 (Why is no real title available?)

This page was built for publication: Randomness – A Computational Complexity Perspective

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