On the Complexity of Hardness Amplification

DOI10.1109/TIT.2008.928988zbMath1322.68084OpenAlexW2072124641MaRDI QIDQ3604852

Shi-Chun Tsai, Hsin-Lung Wu, Chi-Jen Lu

Publication date: 24 February 2009

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/tit.2008.928988

Mathematics Subject Classification ID

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

Related Items (9)

Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ Improved hardness amplification in NP ⋮ Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? ⋮ Query complexity in errorless hardness amplification ⋮ Unnamed Item ⋮ 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 ⋮ Advice Lower Bounds for the Dense Model Theorem

This page was built for publication: On the Complexity of Hardness Amplification