TY - CHAP
T1 - Inapproximability results for computational problems on lattices
AU - Khot, Subhash
N1 - Publisher Copyright:
© 2009, Springer-Verlag Berlin Heidelberg.
PY - 2010
Y1 - 2010
N2 - In this article, we present a survey of known inapproximability results for computational problems on lattices, viz. the Shortest Vector Problem (SVP), the Closest Vector Problem (CVP), the Closest Vector Problem with Preprocessing (CVPP), the Covering Radius Problem (CRP), the Shortest Independent Vectors Problem (SIVP), and the Shortest Basis Problem (SBP).
AB - In this article, we present a survey of known inapproximability results for computational problems on lattices, viz. the Shortest Vector Problem (SVP), the Closest Vector Problem (CVP), the Closest Vector Problem with Preprocessing (CVPP), the Covering Radius Problem (CRP), the Shortest Independent Vectors Problem (SIVP), and the Shortest Basis Problem (SBP).
UR - http://www.scopus.com/inward/record.url?scp=85016192576&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85016192576&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-02295-1_14
DO - 10.1007/978-3-642-02295-1_14
M3 - Chapter
AN - SCOPUS:85016192576
T3 - Information Security and Cryptography
SP - 453
EP - 473
BT - Information Security and Cryptography
PB - Springer International Publishing
ER -