loading...
Hardness Amplification within NP against Deterministic Algorithms
June 22-June 26
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2008.172008 IEEE 23rd Annual Conference on C ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Parikshit Gopalan, Venkatesan Guruswami, "Hardness Amplification within NP against Deterministic Algorithms," Computational Complexity, Annual IEEE Conference on, pp. 19-30, 2008 IEEE 23rd Annual Conference on Computational Complexity, 2008.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2008.17,
author = {Parikshit Gopalan and Venkatesan Guruswami},
title = {Hardness Amplification within NP against Deterministic Algorithms},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2008},
issn = {1093-0159},
pages = {19-30},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2008.17},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - Hardness Amplification within NP against Deterministic Algorithms
SN - 1093-0159
SP19
EP30
A1 - Parikshit Gopalan,
A1 - Venkatesan Guruswami,
PY - 2008
KW - NP
KW - Hardness Amplication
KW - Derandomization
KW - Error-Correcting Codes
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
We study the average-case hardness of the class NP against deterministic polynomial time algorithms. We prove that there exists some constant μ > 0 such that if there is some language in NP for which no deterministic polynomial time algorithm can decide L correctly on a 1 − (log n)−μ fraction of inputs of length n, then there is a language L' in NP for which no deterministic polynomial time algorithm can decide L' correctly on a 3/4 + (log n)−μ fraction of inputs of length n. In coding theoretic terms, we give a construction of a monotone code that can be uniquely decoded up to error rate 1/4 by a deterministic local decoder.
Index Terms:
NP, Hardness Amplication, Derandomization, Error-Correcting Codes
Citation:
Parikshit Gopalan, Venkatesan Guruswami, "Hardness Amplification within NP against Deterministic Algorithms," ccc, pp.19-30, 2008 IEEE 23rd Annual Conference on Computational Complexity, 2008
Usage of this product signifies your acceptance of the Terms of Use.