Hardness amplification within NP against deterministic algorithms

DOI10.1016/J.JCSS.2010.06.008MaRDI QIDQ619904zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

monotone functionsexpander graphsnoise sensitivityerror-correcting codesaverage-case hardnesshardness amplificationNPP

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)

Recommendations

• Improved hardness amplification in NP
• Using Nondeterminism to Amplify Hardness
• Hardness amplification within NP
• Using nondeterminism to amplify hardness
• On uniform amplification of hardness in NP

Cites work

• scientific article; zbMATH DE number 1306886 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 5485571 (Why is no real title available?)
• Approximate list-decoding of direct product codes and uniform hardness amplification
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• Expander graphs and their applications
• Generalized minimum distance decoding
• Hardness Amplification Via Space-Efficient Direct Products
• Hardness amplification within NP
• Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
• List decoding algorithms for certain concatenated codes
• On Worst‐Case to Average‐Case Reductions for NP Problems
• On Yao's XOR-lemma
• On uniform amplification of hardness in NP
• Pseudorandom generators without the XOR lemma
• Pseudorandomness and average-case complexity via uniform reductions
• Reducibility among combinatorial problems
• The complexity of constructing pseudorandom generators from hard functions
• The complexity of theorem-proving procedures
• Using Nondeterminism to Amplify Hardness
• BPP has subexponential time simulations unless EXPTIME has publishable proofs

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)