TR07-089 Authors: Parikshit Gopalan, Venkatesan Guruswami

Publication: 24th September 2007 10:02

Downloads: 2025

Keywords:

We 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.