Hardness magnification for natural problems

DOI10.1109/FOCS.2018.00016MaRDI QIDQ6944398zbMATH OpenFDO

Authors Igor C. Oliveira, Rahul Santhanam

Publication date 12 August 2025

Full work available at URL http://wrap.warwick.ac.uk/129369/1/WRAP-hardness-magnification-natural-problems-Oliveira-2018.pdf

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(6)

• On the consistency of circuit lower bounds for non-deterministic time
• On black-box meta complexity and function inversion
• Regularization of low error PCPs and an application to MCSP
• On one-way functions, the worst-case hardness of time-bounded Kolmogorov complexity, and computational depth
• Learning algorithms from circuit lower bounds
• One-tape Turing machine and branching program lower bounds for MCSP

This page was built for publication: Hardness magnification for natural problems

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