Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SUM CHECK PROTOCOL:
Reports tagged with Sum Check Protocol:
TR11-119 | 4th September 2011
Subhash Khot, Preyas Popat, Nisheeth Vishnoi

2^{\log^{1-\epsilon} n} Hardness for Closest Vector Problem with Preprocessing

We prove that for an arbitrarily small constant \eps>0, assuming NP\not \subseteqDTIME(2^{{\log^{O(1/\epsilon)} n}}), the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor better than 2^{\log ^{1-\epsilon}n}. This improves upon the previous hardness factor of (\log n)^\delta for some $\delta ... more >>>




ISSN 1433-8092 | Imprint