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?
  • 1
    $\begingroup$ Can you provide a reference for your first statement? If you have Ajtai's results in mind, they do not establish average case hardness, see the discussion in Bogdanov and Trevisan, for example: dimacs.rutgers.edu/~adib/pubs/redux-sicomp.pdf. The existence of problems which are hard for samplable distributions is open afaik. $\endgroup$ – Sasho Nikolov May 1 '13 at 17:35
  • $\begingroup$ Yes, I was thinking of Ajtai's results, in particular the random self-reducibility of hard instances: portal.acm.org/citation.cfm?id=276705 It is apparent that my knowledge in this area is lacking. Please feel free to edit the question or suggest a more accurate opening sentence. For now I will revise it to include only the random self-reducibility. $\endgroup$ – Ross Snider May 1 '13 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.