ECCC-Report TR07-089https://eccc.weizmann.ac.il/report/2007/089Comments and Revisions published for TR07-089en-usMon, 24 Sep 2007 10:02:01 +0200
Paper TR07-089
| Deterministic Hardness Amplification via Local GMD Decoding |
Parikshit Gopalan,
Venkatesan Guruswami
https://eccc.weizmann.ac.il/report/2007/089We study the average-case hardness of the class NP against
deterministic polynomial time algorithms. We prove that there exists
some constant $\mu > 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)^{-\mu}$ 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)^{-\mu}$ 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.
Mon, 24 Sep 2007 10:02:01 +0200https://eccc.weizmann.ac.il/report/2007/089