Average-Case Complexity: Levin's Distributional Problems, AvgP, and Cryptographic ImplicationsA deep examination of average-case complexity—Levin's theory of distributional NP-completeness, the class AvgP, and why cryptography needs hard-on-average problems.
