Hardness amplification within NP against deterministic algorithms
DOI10.1016/J.JCSS.2010.06.008zbMATH Open1214.68171OpenAlexW2086334105MaRDI QIDQ619904FDOQ619904
Authors: Parikshit Gopalan, Venkatesan Guruswami 
Publication date: 18 January 2011
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2010.06.008
Recommendations
monotone functionsexpander graphsnoise sensitivityerror-correcting codesaverage-case hardnesshardness amplificationNPP
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Reducibility among combinatorial problems
- List decoding algorithms for certain concatenated codes
- Expander graphs and their applications
- The complexity of theorem-proving procedures
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- The complexity of constructing pseudorandom generators from hard functions
- Pseudorandomness and average-case complexity via uniform reductions
- 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
- Title not available (Why is that?)
- Hardness amplification within NP
- On uniform amplification of hardness in NP
- Using Nondeterminism to Amplify Hardness
- Hardness Amplification Via Space-Efficient Direct Products
- Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
- Approximate list-decoding of direct product codes and uniform hardness amplification
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Generalized minimum distance decoding
Cited In (13)
- On uniform amplification of hardness in NP
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
- Hardness Amplification Via Space-Efficient Direct Products
- Improving on Gutfreund, Shaltiel, and Ta-Shma's paper ``If NP languages are hard on the worst-case, then it is easy to find their hard instances
- Improved hardness amplification in NP
- Using Nondeterminism to Amplify Hardness
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
- (Nondeterministic) hardness vs. non-malleability
- Query complexity in errorless hardness amplification
- Approximate list-decoding of direct product codes and uniform hardness amplification
- Hardness amplification via space-efficient direct products
- A zero-one law for RP and derandomization of AM if NP is not small
- UG-hardness to NP-hardness by losing half
This page was built for publication: Hardness amplification within NP against deterministic algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q619904)
