ALMOST POLYNOMIAL FACTOR HARDNESS FOR CLOSEST VECTOR PROBLEM WITH PREPROCESSING

作者：Khot Subhash A^*; Popat Preyas; Vishnoi Nisheeth K

来源：SIAM Journal on Computing, 2014, 43(3): 1184-1205.

DOI：10.1137/130919623

• hardness of approximation
• closest vector problem
• smooth label cover
• sum check protocol

We prove that for an arbitrarily small constant epsilon > 0, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor 2(log1-epsilon) (n), under the assumption that NP not subset of SIZE(2log(O(1/epsilon)) (n)).

• 出版日期2014
• 单位Microsoft