CS Events

Qualifying Exam

One way functions and a conditional variant of MKTP


Download as iCal file

Friday, May 07, 2021, 09:30am - 11:00am


Speaker: Harsha Srimath Tirumala

Location : Remote via Webex


Prof. Eric Allender (advisor)

Prof. Michael Saks

Prof. Sepehr Assadi

Prof. Santosh Nagarakatte

Event Type: Qualifying Exam

Abstract: One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence for the average-case hardness of some NP-complete problem. In our work, we make progress on this question by studying a conditional variant of the Minimum KT-complexity Problem (MKTP), which we call McKTP, as follows : 1. First, we prove that if McKTP is average-case hard on a polynomial fraction of its instances, then there exist OWFs. 2. Then, we observe that McKTP is NP-complete under polynomial-time randomized reductions. That is, there are NP-complete problems whose average-case hardness implies the existence of OWFs. 3. Finally, we prove that the existence of OWFs implies the nontrivial average-case hardness of McKTP. Thus the existence of OWFs is inextricably linked to the average-case hardness of this NP-complete problem.



Meeting number: 120 918 7286
Password: KuXJxTGc826

Join by video system
Dial This email address is being protected from spambots. You need JavaScript enabled to view it.
You can also dial and enter your meeting number.

Join by phone
+1-650-429-3300 USA Toll
Access code: 120 918 7286