Department Events
The department runs a variety of seminars, workshops and colloquia. See upcoming events below. You are also welcome to sign up to the seminar mailing list.
For visiting the department, see the map of campus, directions, and accommodation recommendations.
(Be reminded that the University of Warwick is not, surprisingly, located in the town of Warwick.)
Oxford-Warwick Complexity Meeting: Rafael Pass (Cornell)
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
More…