NP-hardness of learning programs and partial MCSP

DOI10.1109/FOCS54457.2022.00095MaRDI QIDQ6942993zbMATH OpenFDO

Authors Shuichi Hirahara

Publication date 15 August 2025

Full work available at URL https://doi.org/10.1109/FOCS54457.2022.00095

Mathematics Subject Classification ID

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

Cited in

(9)

• Regularization of low error PCPs and an application to MCSP
• One-way functions and pKt complexity
• On one-way functions, the worst-case hardness of time-bounded Kolmogorov complexity, and computational depth
• Lower bounds for Levin-Kolmogorov complexity
• Hardness along the boundary: towards one-way functions from the worst-case hardness of time-bounded Kolmogorov complexity
• Gap MCSP is not (Levin) NP-complete in obfustopia
• NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
• NP-hardness of approximating meta-complexity: a cryptographic approach
• Consequences of randomized reductions from SAT to time-bounded Kolmogorov complexity

This page was built for publication: NP-hardness of learning programs and partial MCSP

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