Average-Case-Complexity

• Average-Case Complexity: Levin's Distributional Problems, AvgP, and Cryptographic Implications · 2019-10-20

  A deep examination of average-case complexity—Levin's theory of distributional NP-completeness, the class AvgP, and why cryptography needs hard-on-average problems.