Hardness amplification within NP against deterministic algorithms

DOI10.1016/j.jcss.2010.06.008zbMath1214.68171OpenAlexW2086334105MaRDI QIDQ619904

Venkatesan Guruswami, Parikshit Gopalan

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

noise sensitivitymonotone functionshardness amplificationerror-correcting codesexpander graphsaverage-case hardnessNPP

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 (3)

Query complexity in errorless hardness amplification ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(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
• On Yao’s XOR-Lemma
• List decoding algorithms for certain concatenated codes
• Expander graphs and their applications
• 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
• On uniform amplification of hardness in NP
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• Reducibility among Combinatorial Problems
• Using Nondeterminism to Amplify Hardness
• The complexity of theorem-proving procedures
• Generalized minimum distance decoding
• 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: Hardness amplification within NP against deterministic algorithms