Using nondeterminism to amplify hardness

DOI10.1145/1007352.1007389MaRDI QIDQ3580969zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(9)

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

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)