<p>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.</p>

<p>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.</p>

<p>So, really two questions:</p>

<ul>
<li>What is known of this problem?</li>
<li>Is there a canonical name for this problem?</li>
</ul>

CC BY-SA 3.0
2013-05-01T17:35:41.787Z
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: http://dimacs.rutgers.edu/~adib/pubs/redux-sicomp.pdf. The existence of problems which are hard for samplable distributions is open afaik.
Sasho Nikolov
CC BY-SA 3.0
2013-05-01T18:19:36.240Z
Yes, I was thinking of Ajtai's results, in particular the random self-reducibility of hard instances: http://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.
Ross Snider
<optimization><average-case-complexity><lattice><cc.complexity-theory>
Closest Vector Problem with sparse basis and target vector
Ross Snider
# Closest Vector Problem with sparse basis and target vector

(Asked by: username_0 on 2013-05-01)

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?

**Tags:** optimization, average-case-complexity, lattice, cc.complexity-theory
> **Comments:**
> **username_1**: 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: http://dimacs.rutgers.edu/~adib/pubs/redux-sicomp.pdf. The existence of problems which are hard for samplable distributions is open afaik.  
> **username_0**: Yes, I was thinking of Ajtai's results, in particular the random self-reducibility of hard instances: http://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.  

---

## 0 answers

