Average Case Complexity, Revisited

DOI10.1007/978-3-642-22670-0_29zbMath1343.68114OpenAlexW1603569343MaRDI QIDQ3088195

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_29

zbMATH Keywords

average-case complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

On expected polynomial runtime in cryptography ⋮ Notes on Levin’s Theory of Average-Case Complexity

Cites Work

• On the theory of average case complexity
• Notes on Levin’s Theory of Average-Case Complexity
• Average-Case Complexity
• Average Case Complete Problems
• A Pseudorandom Generator from any One-way Function
• Foundations of Cryptography
• Computational Complexity

This page was built for publication: Average Case Complexity, Revisited