Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR07-089 | 13th September 2007 00:00

#### Deterministic Hardness Amplification via Local GMD Decoding

TR07-089
Authors: Parikshit Gopalan, Venkatesan Guruswami
Publication: 24th September 2007 10:02
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint