Past 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
You can also dial and enter your meeting number.

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