On the Quantitative Hardness of CVP

Bennett, H; Stephens-Davidowitz, N; Golovnev, A

Bennett, H (reprint author), NYU, Courant Inst, New York, NY 10003 USA.

2017 IEEE 58TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2017; ( ): 13

Abstract

For odd integers p >= 1 (and p = infinity), we show that the Closest Vector Problem in the l(p) norm (CVPp) over rank n lattices cannot be solved i......

Full Text Link