On uniform amplification of hardness in NP

DOI10.1145/1060590.1060595zbMath1192.68304OpenAlexW2135456059MaRDI QIDQ3581414

Luca Trevisan

Publication date: 16 August 2010

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

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

Mathematics Subject Classification ID

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

Related Items (8)

Hardness amplification within NP against deterministic algorithms ⋮ Query complexity in errorless hardness amplification ⋮ On derandomizing Yao's weak-to-strong OWF construction ⋮ Complexity of hard-core set proofs ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification ⋮ Computational Randomness from Generalized Hardcore Sets ⋮ List-Decoding with Double Samplers

This page was built for publication: On uniform amplification of hardness in NP