Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-201 | 4th December 2024 17:55

On one-way functions and the average time complexity of almost-optimal compression

RSS-Feed




TR24-201
Authors: Marius Zimand
Publication: 5th December 2024 12:39
Downloads: 106
Keywords: 


Abstract:

We show that one-way functions exist if and only there exists an efficient distribution relative to which almost-optimal compression is hard on average. The result is obtained by combining a theorem of Ilango, Ren, and Santhanam [STOC 2022] and one by Bauwens and Zimand [JACM, 2023].



ISSN 1433-8092 | Imprint