What is a sparse subset?

Question

In a work about fully homomorphic encryption I found usage of the expression: "sparse subset", as in:

Our hint will consist of a set of vectors that has a (secret) sparse subset of vectors whose sum is v$_J^{sk^*}$

How exactly is such sparseness defined in general? Or it is a notion created by Craig Gentry and it just means that there are not that many vectors and that distances between them are fairly big?

"Sparse" is a standard term; see http://en.wikipedia.org/wiki/Sparse_matrix. — Qiaochu Yuan, Nov 14 '14 at 01:05
@QiaochuYuan what does that mean in terms of subsets of vectors then? — Golob, Nov 14 '14 at 01:16
I think it means it's a small subset of vectors (relative to the size of the set of vectors). — Qiaochu Yuan, Nov 14 '14 at 01:29

score 1 · Accepted Answer · answered Nov 14 '14 at 02:17

1

Sparse here means the following: $S\subseteq T$ (where $T$ is finite, and has size $n=|T|$ for $n$ considered as going to infinity) is sparse if $\frac{|S|}{|T|} = o(1)$. See e.g. an example on the last line of p.16.

answered Nov 14 '14 at 02:17

Clement C.

67,323

What is a sparse subset?

1 Answers1