Beyond Natural Proofs: Hardness Magnification and Locality

DOI10.1145/3538391MaRDI QIDQ5889786OpenAlexWikidataFDO

Authors Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam

Publication date 27 April 2023

Published in Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

circuit complexitynatural proofshardness magnification

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Beyond natural proofs: hardness magnification and locality
• Hardness magnification near state-of-the-art lower bounds
• Hardness magnification near state-of-the-art lower bounds
• Weak lower bounds on resource-bounded compression imply strong separations of complexity classes

Cited in

(4)

• Localizability of the approximation method
• Unprovability of strong complexity lower bounds in bounded arithmetic
• Hardness Amplification Proofs Require Majority
• Input locality and hardness amplification

This page was built for publication: Beyond Natural Proofs: Hardness Magnification and Locality

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