Unexpected hardness results for Kolmogorov complexity under uniform reductions

DOI10.1145/3357713.3384251MaRDI QIDQ5144987zbMATH OpenOpenAlexFDO

Authors Shuichi Hirahara

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3357713.3384251

zbMATH Keywords

(black-box) reductionsKolmogorov complexitypseudorandomness

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Power from Random Strings
• On randomized reductions to the random strings
• Lower bounds for reducibility to the Kolmogorov random strings
• STACS 2004
• Limits on the Computational Power of Random Strings

Cited in

(14)

• Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
• scientific article; zbMATH DE number 7561748 (Why is no real title available?)
• scientific article; zbMATH DE number 7758317 (Why is no real title available?)
• Some games on Turing machines and power from random strings
• ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS
• NP-hardness of approximating meta-complexity: a cryptographic approach
• Constructive separations and their consequences
• On randomized reductions to the random strings
• Exact search-to-decision reductions for time-bounded Kolmogorov complexity
• On the computational power of C-random strings
• Consequences of randomized reductions from SAT to time-bounded Kolmogorov complexity
• NP-hardness of approximating meta-complexity: a cryptographic approach
• Lower bounds for Levin-Kolmogorov complexity
• Kolmogorov complexity characterizes statistical zero knowledge

This page was built for publication: Unexpected hardness results for Kolmogorov complexity under uniform reductions

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