Average case complexity, revisited

DOI10.1007/978-3-642-22670-0_29MaRDI QIDQ3088195zbMATH 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_29

zbMATH Keywords

average-case complexity

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 5081744
• On the theory of average case complexity
• scientific article; zbMATH DE number 1072538
• All natural NP-complete problems have average-case complete versions
• scientific article; zbMATH DE number 1008518

Cites work

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

Cited in

(12)

• On expected polynomial runtime in cryptography
• Notes on Levin's theory of average-case complexity
• Randomizing Reductions of Search Problems
• scientific article; zbMATH DE number 5081744 (Why is no real title available?)
• Average-Case Complexity
• scientific article; zbMATH DE number 1313596 (Why is no real title available?)
• scientific article; zbMATH DE number 1008511 (Why is no real title available?)
• scientific article; zbMATH DE number 1008518 (Why is no real title available?)
• scientific article; zbMATH DE number 1180007 (Why is no real title available?)
• Malign distributions for average case circuit complexity
• scientific article; zbMATH DE number 7515768 (Why is no real title available?)
• All natural NP-complete problems have average-case complete versions

This page was built for publication: Average case complexity, revisited

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