Improved hardness amplification in NP
From MaRDI portal
Publication:868960
DOI10.1016/J.TCS.2006.10.009zbMATH Open1110.68047OpenAlexW2064640176MaRDI QIDQ868960FDOQ868960
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
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Foundations of Cryptography
- The complexity of constructing pseudorandom generators from hard functions
- On the Complexity of Hardness Amplification
- Title not available (Why is that?)
- Pseudorandom generators without the XOR lemma
- Title not available (Why is that?)
- On Worst‐Case to Average‐Case Reductions for NP Problems
- On Yao’s XOR-Lemma
- Pseudorandom generators for space-bounded computation
- Improved pseudorandom generators for combinatorial rectangles
- Hardness amplification within NP
- Using nondeterminism to amplify hardness
Cited In (3)
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)
