On the Complexity of Hardness Amplification
From MaRDI portal
Publication:3604852
DOI10.1109/TIT.2008.928988zbMATH Open1322.68084OpenAlexW2072124641MaRDI QIDQ3604852FDOQ3604852
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
Recommendations
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
- Improved hardness amplification in NP
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- Hardness Amplification Proofs Require Majority
- Impossibility Results on Weakly Black-Box Hardness Amplification
- On the Complexity of Hard-Core Set Constructions
- Complexity of hard-core set proofs
- Using Nondeterminism to Amplify Hardness
- Title not available (Why is that?)
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
- Query complexity in errorless hardness amplification
- Advice lower bounds for the dense model theorem
- Query complexity in errorless hardness amplification
- 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)
