Notes on Levin’s Theory of Average-Case Complexity

DOI10.1007/978-3-642-22670-0_21zbMath1343.68111OpenAlexW2275958883MaRDI QIDQ3088187

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_21

zbMATH Keywords

reductionsaverage-case complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

Generalized juntas and NP-hard sets ⋮ On expected polynomial runtime in cryptography ⋮ Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey ⋮ Frequency of correctness versus average polynomial time ⋮ Average Case Complexity, Revisited

Cites Work

• Unnamed Item
• Unnamed Item
• On the theory of average case complexity
• Average Case Complexity, Revisited
• Average Case Complete Problems
• Foundations of Cryptography
• Foundations of Cryptography
• On the Computational Complexity of Algorithms
• The NP-completeness column: An ongoing guide
• Computational Complexity

This page was built for publication: Notes on Levin’s Theory of Average-Case Complexity