On randomized reductions to the random strings

DOI10.4230/LIPICS.CCC.2022.29MaRDI QIDQ6568372zbMATH OpenFDO

Authors Michael Saks, Rahul Santhanam

Publication date 5 July 2024

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

zbMATH Keywords

Kolmogorov complexityrandomized reductions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Lower bounds for reducibility to the Kolmogorov random strings
• Limitations of efficient reducibility to the Kolmogorov random strings
• STACS 2004
• Unexpected hardness results for Kolmogorov complexity under uniform reductions
• Power from Random Strings

Cited in

(6)

• Unexpected hardness results for Kolmogorov complexity under uniform reductions
• Gap MCSP is not (Levin) NP-complete in obfustopia
• Impagliazzo's worlds through the Lens of conditional Kolmogorov complexity
• Consequences of randomized reductions from SAT to time-bounded Kolmogorov complexity
• SAT reduces to the minimum circuit size problem with a random oracle
• Kolmogorov complexity characterizes statistical zero knowledge

This page was built for publication: On randomized reductions to the random strings

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