Abstract

Meta-complexity refers to the study of the computational complexity of computing natural complexity measures, such as time-bounded Kolmogorov complexity and the minimal circuit size. Despite decades of interest, important basic questions about these problems remain unresolved.

In this talk I will present few open questions in the field, and their implications on cryptography.