|
|||||
|
|
Hardness of Approximating the Closest Vector Problem with Pre-Processing |
|
| Authors: | Mikhail Alekhnovich Subhash A. Khot Guy Kindler Nisheeth K. Vishnoi |
| Affiliation: | 1. Institute for Advanced Study, Princeton, NJ, 08540, USA 2. Computer Science Department, Courant Institute of Mathematical Sciences, New York University, New York, NY, 10012, USA 3. School of Computer Science and Engineering, The Hebrew University of Jerusalem, Ross Building, Givat Ram Campus, 91904, Jerusalem, Israel 4. Microsoft Research India, 196/36 2nd Main Sadashivnagar, Bangalore, 560080, India |
| Abstract: | We show that the pre-processing versions of the closest vector problem and the nearest codeword problem are NP{mathsf {NP}} -hard to approximate within any constant factor. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |