Characterizing average-case complexity of PH by worst-case meta-complexity

DOI10.1109/FOCS46700.2020.00014MaRDI QIDQ6944043zbMATH OpenFDO

Authors Shuichi Hirahara

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS46700.2020.00014

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06)

Cited in

(5)

• Exact search-to-decision reductions for time-bounded Kolmogorov complexity
• Impagliazzo's worlds through the Lens of conditional Kolmogorov complexity
• Stretching demi-bits and nondeterministic-secure pseudorandomness
• Lower bounds for Levin-Kolmogorov complexity
• SAT reduces to the minimum circuit size problem with a random oracle

This page was built for publication: Characterizing average-case complexity of PH by worst-case meta-complexity

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