Hardness amplification within NP against deterministic algorithms
type: Item
instance of: scholarly article
title: Hardness amplification within NP against deterministic algorithms
zbMATH Open document ID: 1214.68171
author: Parikshit Gopalan
author: Venkatesan Guruswami
published in: Journal of Computer and System Sciences
publication date: 2011-01-18T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5838478
zbMATH Keywords: average-case hardness
zbMATH Keywords: hardness amplification
zbMATH Keywords: error-correcting codes
zbMATH Keywords: NP
zbMATH Keywords: P
zbMATH Keywords: monotone functions
zbMATH Keywords: expander graphs
zbMATH Keywords: noise sensitivity
MaRDI profile type: Publication
full work available at URL: j.jcss.2010.06.008
OpenAlex ID: W2086334105
cites work: The complexity of theorem-proving procedures
cites work: Reducibility among Combinatorial Problems
cites work: Hardness amplification within NP
cites work: Using Nondeterminism to Amplify Hardness
cites work: On uniform amplification of hardness in NP
cites work: Pseudorandom generators without the XOR lemma
cites work: Pseudorandomness and average-case complexity via uniform reductions
cites work: On Worst‐Case to Average‐Case Reductions for NP Problems
cites work: The complexity of constructing pseudorandom generators from hard functions
cites work: On Yao’s XOR-Lemma
cites work: \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
cites work: Q4252738
cites work: Q4526985
cites work: Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification
cites work: Q5302082
cites work: Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
cites work: Generalized minimum distance decoding
cites work: Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
cites work: Hardness Amplification Via Space-Efficient Direct Products
cites work: Expander graphs and their applications
cites work: List decoding algorithms for certain concatenated codes
DOI: 10.1016/J.JCSS.2010.06.008
description: scientific article; zbMATH DE number 5838478