Thumbnail
Access Restriction
Subscribed

Author Khot, Subhash
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2005
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Approximation algorithms ♦ Cryptography ♦ Hardness of approximation ♦ Lattices ♦ Shortest vector problem
Abstract Let $\textit{p}$ > 1 be any fixed real. We show that assuming NP ⊈ RP, there is no polynomial time algorithm that approximates the Shortest Vector Problem (SVP) in $ℓ\textit{p}$ norm within a constant factor. Under the stronger assumption NP ⊈ $RTIME(2\textit{poly}(log$ $\textit{n})),$ we show that there is no polynomial-time algorithm with approximation ratio 2(log $n)^{1/2™ε}}$ where $\textit{n}$ is the dimension of the lattice and ε > 0 is an arbitrarily small constant.We first give a new (randomized) reduction from Closest Vector Problem (CVP) to SVP that achieves $\textit{some}$ constant factor hardness. The reduction is based on BCH Codes. Its advantage is that the SVP instances produced by the reduction behave well under the augmented tensor product, a new variant of tensor product that we introduce. This enables us to boost the hardness factor to 2(log $n)^{1/2-ε}}.$
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 52
Issue Number 5
Page Count 20
Starting Page 789
Ending Page 808


Open content in new tab

   Open content in new tab
Source: ACM Digital Library