$2^{\log^{1-\eps} n}$ Hardness for Closest Vector Problem with Preprocessing

Subhash Khot Preyas Popat Nisheeth K. Vishnoi

Published in: CoRR (2011)

Keyphrases

preprocessing
post processing
feature extraction
feature vectors
vector space
np hard
nearest neighbor
phase transition
itemsets
np complete
preprocessing phase
sparse matrix
preprocessing step
learning theory
information theoretic
data sets
data points
image processing
information retrieval
databases