The Closest Vector Problem (and related problems) is random self-reducible and in general is NP-Hard, making it a useful tool in cryptography research and post-quantum public key crypto. For a variety of reasons (e.g. key size, protocol speed) it might be interesting to consider CVP instances where the vectors are sparse. In fact, in solving an algorithmic problem that has come up separately from cryptographic research, I have encountered what I am currently modeling as a sparse CVP problem.
Suppose we have a high dimensional (N >> 0) closest vector problem where each of the basis vectors and the target vector all have low (log N) support. What is known in the literature in this case? Does the problem become harder, by the compactness of the input? Does the sparsity of the vectors enable solutions to be found or approximated more quickly in the limit? A rudimentary literature search was not able to find relevant papers.
So, really two questions:
- What is known of this problem?
- Is there a canonical name for this problem?