Friday, February 19, 2021 - 1:00pm to 2:30pm

Location:

Please email dlehto@mit.edu for Zoom Link

Speaker:

Rafael Pass

Seminar group:

Abstract:
We prove the equivalence of two fundamental problems in the theory of computing.
For every polynomial t(n)>2n, the following are equivalent:

- Cryptographic one-way functions exists;
- The t-time bounded Kolmogorov Complexity problem is mildly hard-on-average.