Guest Column: On Cryptography and Meta-Complexity

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. This survey explores some of the recent connections between meta-complexity and cryptography, focusing on how tools from one domain can help solving long-standing questions in the other.