Beyond Natural Proofs: Hardness Magnification and Locality

DOI10.1145/3538391OpenAlexW2991175439WikidataQ113769992 ScholiaQ113769992MaRDI QIDQ5889786

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

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)

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