Notes on Levin's theory of average-case complexity

DOI10.1007/978-3-642-22670-0_21MaRDI QIDQ3088187zbMATH 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_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)

Recommendations

• Average case complexity, revisited
• scientific article; zbMATH DE number 1072538
• On the theory of average case complexity
• Structural average case complexity
• scientific article; zbMATH DE number 1008518

Cites work

• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Average Case Complete Problems
• Average case complexity, revisited
• Computational Complexity
• Foundations of Cryptography
• Foundations of Cryptography
• On the Computational Complexity of Algorithms
• On the theory of average case complexity
• The NP-completeness column: An ongoing guide

Cited in

(7)

• Generalized juntas and NP-hard sets
• On the average complexity of the $k$-level
• Average case complexity theory
• Frequency of correctness versus average polynomial time
• Average case complexity, revisited
• On expected polynomial runtime in cryptography
• Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey

This page was built for publication: Notes on Levin's theory of average-case complexity

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