Using nondeterminism to amplify hardness

DOI10.1145/1007352.1007389zbMath1192.68294OpenAlexW1980327536MaRDI QIDQ3580969

Emanuele Viola, Alexander D. Healy, Salil P. 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)

Related Items

Improved hardness amplification in NP ⋮ On derandomizing Yao's weak-to-strong OWF construction

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