Coronavirus (Covid-19): Latest updates and information
Skip to main content Skip to navigation

Intelligent and Adaptive Systems Research Group Seminars and Events

Forthcoming Events

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

Wed, Sep 30 Today Fri, Oct 02 Jump to any date
Oxford-Warwick Complexity Meeting: Rafael Pass (Cornell)
Online seminar

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