Improved hardness amplification in NP

DOI10.1016/j.tcs.2006.10.009zbMath1110.68047OpenAlexW2064640176MaRDI QIDQ868960

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

Publication date: 26 February 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.10.009

zbMATH Keywords

computational complexitypseudorandom generatorhardness amplificationNP

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Paradigms for Unconditional Pseudorandom Generators ⋮ Query complexity in errorless hardness amplification

Cites Work

• Unnamed Item
• Unnamed Item
• Pseudorandom generators for space-bounded computation
• The complexity of constructing pseudorandom generators from hard functions
• Improved pseudorandom generators for combinatorial rectangles
• On Yao’s XOR-Lemma
• Using nondeterminism to amplify hardness
• On the Complexity of Hardness Amplification
• Foundations of Cryptography
• On Worst‐Case to Average‐Case Reductions for NP Problems
• Hardness amplification within NP
• Pseudorandom generators without the XOR lemma

This page was built for publication: Improved hardness amplification in NP