On the Complexity of Hardness Amplification

DOI10.1109/TIT.2008.928988MaRDI QIDQ3604852zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Theory of Cryptography
• Impossibility Results on Weakly Black-Box Hardness Amplification
• Using Nondeterminism to Amplify Hardness
• Using nondeterminism to amplify hardness
• Hardness Amplification Proofs Require Majority

Cited in

(20)

• On uniform amplification of hardness in NP
• Limitations of Hardness vs. Randomness under Uniform Reductions
• Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
• Theory of Cryptography
• Counterexamples to hardness amplification beyond negligible
• Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
• Improved hardness amplification in NP
• Complexity of hard-core set proofs
• Hardness Amplification Proofs Require Majority
• Impossibility Results on Weakly Black-Box Hardness Amplification
• On the Complexity of Hard-Core Set Constructions
• Using Nondeterminism to Amplify Hardness
• Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
• scientific article; zbMATH DE number 7758312 (Why is no real title available?)
• Query complexity in errorless hardness amplification
• Query complexity in errorless hardness amplification
• Advice lower bounds for the dense model theorem
• The complexity of constructing pseudorandom generators from hard functions
• Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?
• Using nondeterminism to amplify hardness

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

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