On randomized reductions to the random strings

DOI10.4230/LIPICS.CCC.2022.29MaRDI QIDQ6568372FDOQ6568372

Authors: Michael Saks, Rahul Santhanam 

Publication date: 5 July 2024

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

zbMATH Keywords

Kolmogorov complexityrandomized reductions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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)