#Levin

1 post in tag “Levin”.

• 

  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.