Kolmogorov and One-Way Functions - Talk 1/5

Explore the fundamental connections between Kolmogorov complexity and one-way functions in this 14-minute conference talk from TCC 2024. Delve into theoretical computer science concepts as part of a comprehensive five-talk session chaired by Prashant Nalini Vasudevan. Examine how Kolmogorov complexity theory intersects with cryptographic primitives, particularly one-way functions, which form the foundation of modern cryptography. Gain insights into cutting-edge research presented at one of the premier venues for theoretical cryptography, where leading researchers discuss the mathematical underpinnings of computational complexity and cryptographic security assumptions.