Improved hardness amplification in NP

DOI10.1016/J.TCS.2006.10.009MaRDI QIDQ868960zbMATH OpenOpenAlexFDO

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

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 complexityhardness amplificationNPpseudorandom generator

Mathematics Subject Classification ID

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

Recommendations

• Hardness amplification within NP
• Hardness amplification within NP against deterministic algorithms
• On uniform amplification of hardness in NP
• Hardness amplification in proof complexity
• Hardness Amplification of Optimization Problems
• On the Complexity of Hardness Amplification
• Using Nondeterminism to Amplify Hardness
• Using nondeterminism to amplify hardness
• Direct product hardness amplification
• Hardness amplification and the approximate degree of constant-depth circuits

Cites work

• Foundations of Cryptography
• Hardness amplification within NP
• scientific article; zbMATH DE number 1306886 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• Improved pseudorandom generators for combinatorial rectangles
• On the Complexity of Hardness Amplification
• On Worst‐Case to Average‐Case Reductions for NP Problems
• On Yao's XOR-lemma
• Pseudorandom generators for space-bounded computation
• Pseudorandom generators without the XOR lemma
• The complexity of constructing pseudorandom generators from hard functions
• Using nondeterminism to amplify hardness

Cited in

(5)

• Using nondeterminism to amplify hardness
• Hardness amplification within NP
• Paradigms for Unconditional Pseudorandom Generators
• Hardness amplification within NP against deterministic algorithms
• Query complexity in errorless hardness amplification

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

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