Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR99-016 | 25th April 1999 00:00

Approximating SVP_\infty to within Almost-Polynomial Factors is NP-hard

RSS-Feed




TR99-016
Authors: Irit Dinur
Publication: 2nd June 1999 12:01
Downloads: 2128
Keywords: 


Abstract:

This paper shows SVP_\infty and CVP_\infty to be NP-hard to approximate
to within any factor up to $n^{1/\log\log n}$. This improves on the
best previous result \cite{ABSS} that showed quasi-NP-hardness for
smaller factors, namely $2^{\log^{1-\epsilon}n}$ for any constant
$\epsilon>0$. We show a direct reduction from SAT to these
problems, that combines ideas from \cite{ABSS} and from
\cite{DKS,DKRS}, along with some modifications. Our result is
obtained without relying on the PCP characterization of NP,
although some of our techniques are derived from the proof of the
PCP characterization itself \cite{DFKRS}.



ISSN 1433-8092 | Imprint