Hardness of approximating the Shortest Vector Problem in high ℓp norms

摘要

We present a new hardness of approximation result for the Shortest Vector Problem in ℓp norm (denoted by SVPp). Assuming NP ⊈ ZPP, we show that for every ε>0, there is a constant p(ε) such that for all integers p⩾p(ε), the problem SVPp has no polynomial time approximation algorithm with approximation ratio p1-ε.