Optimal coding theorems in time-bounded Kolmogorov complexity

DOI10.4230/LIPICS.ICALP.2022.92MaRDI QIDQ6560890zbMATH OpenFDO

Authors Zhenjian Lu, Igor C. Oliveira, Marius Zimand

Publication date 24 June 2024

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2022.92

zbMATH Keywords

computational complexityKolmogorov complexityrandomized algorithms

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cited in

(7)

• Hardness along the boundary: towards one-way functions from the worst-case hardness of time-bounded Kolmogorov complexity
• Exact search-to-decision reductions for time-bounded Kolmogorov complexity
• Impagliazzo's worlds through the Lens of conditional Kolmogorov complexity
• Consequences of randomized reductions from SAT to time-bounded Kolmogorov complexity
• One-way functions and pKt complexity
• Lower bounds for Levin-Kolmogorov complexity
• SAT reduces to the minimum circuit size problem with a random oracle

This page was built for publication: Optimal coding theorems in time-bounded Kolmogorov complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6560890)