Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-089 | 13th September 2007 00:00

Deterministic Hardness Amplification via Local GMD Decoding

RSS-Feed




TR07-089
Authors: Parikshit Gopalan, Venkatesan Guruswami
Publication: 24th September 2007 10:02
Downloads: 4318
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