On the average-case complexity of MCSP and its variants
We prove various results on the complexity of MCSP (Minimum Circuit Size Problem) and the related MKTP (Minimum Kolmogorov Time-Bounded Complexity Problem): • We observe that under standard cryptographic assumptions, MCSP has a pseudorandom self-reduction. This is a new notion we define by relaxing...
| Asıl Yazarlar: | , |
|---|---|
| Materyal Türü: | Conference item |
| Baskı/Yayın Bilgisi: |
Schloss Dagstuhl
2017
|