Using nondeterminism to amplify hardness

DOI10.1145/1007352.1007389zbMATH Open1192.68294OpenAlexW1980327536MaRDI QIDQ3580969FDOQ3580969

Authors: Alexander D. Healy, Emanuele Viola, Salil Vadhan 

Publication date: 15 August 2010

Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

Recommendations

• Using Nondeterminism to Amplify Hardness
• Improved hardness amplification in NP
• Hardness amplification within NP
• On the Complexity of Hardness Amplification
• Hardness Amplification Proofs Require Majority

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (9)

• On the Complexity of Hardness Amplification
• On uniform amplification of hardness in NP
• Hardness amplification within NP
• Improved hardness amplification in NP
• Impossibility Results on Weakly Black-Box Hardness Amplification
• Using Nondeterminism to Amplify Hardness
• (Nondeterministic) hardness vs. non-malleability
• Hardness amplification within NP against deterministic algorithms
• On derandomizing Yao's weak-to-strong OWF construction

This page was built for publication: Using nondeterminism to amplify hardness

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