Probabilistic Kolmogorov complexity with applications to average-case complexity

DOI10.4230/LIPICS.CCC.2022.16MaRDI QIDQ6568358zbMATH OpenFDO

Authors Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira

Publication date 5 July 2024

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2022.16

zbMATH Keywords

average-case complexityKolmogorov complexitylearningmeta-complexityworst-case to average-case reductions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited in

(8)

• 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
• NP-hardness of approximating meta-complexity: a cryptographic approach
• 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: Probabilistic Kolmogorov complexity with applications to average-case complexity

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