Data Science Events
Thursday, October 01, 2020
-Export as iCalendar |
Oxford-Warwick Complexity Meeting: Rafael Pass (Cornell)Online seminarTitle: On one-way functions and Kolmogorov complexity 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. In doing so, we present the first natural, and well-studied, computational problem characterizing the feasibility of the central private-key primitives and protocols in Cryptography. Joint work with Yanyi Liu. More information available at https://www.dcs.warwick.ac.uk/~igorcarb/complexity-meetings.html |