Finding errorless pessiland in error-prone heuristica

DOI10.4230/LIPICS.CCC.2022.25MaRDI QIDQ6568368zbMATH OpenFDO

Authors Shuichi Hirahara, Mikito Nanashima

Publication date 5 July 2024

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

zbMATH Keywords

auxiliary-input cryptographyaverage-case complexitylearningmeta-complexityoracle separationrelativization barrier

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited in

(2)

• Hardness along the boundary: towards one-way functions from the worst-case hardness of time-bounded Kolmogorov complexity
• SAT reduces to the minimum circuit size problem with a random oracle

This page was built for publication: Finding errorless pessiland in error-prone heuristica

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