Qualifying Exam

Qualifying Exam One way functions and a conditional variant of MKTP
× Export Event Save iCal Send to Google Calendar Send to Yahoo Calendar Send to Outlook Live Send to Microsoft Outlook Save iCal Preserve formatting in description (only supported in some calendar applications) Close Friday, May 07, 2021, 09:30am - 11:00am

Speaker: Harsha Srimath Tirumala

Location : Remote via Webex

Committee: 

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.

: 

https://rutgers.webex.com/rutgers/j.php?MTID=mb4dceb427c81e1f87936a2ffea31f748

Meeting number: 120 918 7286
Password: KuXJxTGc826

Join by video system
Dial
You can also dial 173.243.2.68 and enter your meeting number.

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