Mathematical Research Data Initiative
Main page
Recent changes
Random page
SPARQL
MaRDI@GitHub
New item
Special pages
In other projects
MaRDI portal item
Discussion
View source
View history
English
Log in

Beyond Natural Proofs: Hardness Magnification and Locality

From MaRDI portal
Publication:5889786
Jump to:navigation, search

DOI10.1145/3538391OpenAlexW2991175439WikidataQ113769992 ScholiaQ113769992MaRDI QIDQ5889786FDOQ5889786


Authors: Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam Edit this on Wikidata


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)

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:5889786&oldid=30760601"
Tools
What links here
Related changes
Printable version
Permanent link
Page information
This page was last edited on 7 March 2024, at 06:06. Warning: Page may not contain recent updates.
Privacy policy
About MaRDI portal
Disclaimers
Imprint
Powered by MediaWiki