Beyond Natural Proofs: Hardness Magnification and Locality

DOI10.1145/3538391OpenAlexW2991175439WikidataQ113769992 ScholiaQ113769992MaRDI QIDQ5889786FDOQ5889786

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)

Cited In (4)

• Hardness Amplification Proofs Require Majority
• Localizability of the approximation method
• Unprovability of strong complexity lower bounds in bounded arithmetic
• 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)