If you want to give a talk at the IAS seminars, please contact Dr. Jonny Foss <jonathan dot foss at warwick dot ac dot uk>.
You can access past talks here .
Thursday, October 01, 2020
Title: 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