On the existence of one-way functions and the hardness of approximating Kolmogorov complexity.

Abstract: One-way functions are functions that are easy to compute and hard to invert. They yield private-key encryption, zero-knowledge proofs, digital signatures, commitment schemes, and other applications in cryptography. They are widely believed to exist but an unconditional proof of this fact implies P \not= NP. I will present a recent characterization due to Ilango, Ren, and Santhanam: there exists a one-way function IFF approximating the Kolmogorov complexity is hard on average with respect to some efficiently samplable distribution.

The paper by Ilango, Ren, and Santhana is available in Proc. STOC 2022, dl.acm.org/doi/10.1145/3519935.3520051 See also by M. Zimand eccc.weizmann.ac.il/report/2024/201/

Computer scienceMathematics

Audience: researchers in the discipline

Seminar on Algorithmic Aspects of Information Theory

Series comments: This online seminar is a follow up of the Dagstuhl Seminar 22301, www.dagstuhl.de/en/program/calendar/semhp/?semnr=22301.