Approximating SVP∞ to within almost-polynomial factors is NP-hard

AbstractWe show SVP∞ and CVP∞ to be NP-hard to approximate to within nc/loglogn for some constant c>0. We show a direct reduction from SAT to these problems, that combines ideas from Arora et al. (Proc. 34th IEEE Symp. on Foundations of Computer Science, 1993, p. 724) and Dinur et al. (Approximating-CVP to within almost-polynomial factors is NP-hard, manuscript, 1999), 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 (STOC: ACM Symposium on Theory of Computing (STOC), 1999)