Given a set of points $S$ which is a subset of a vector space $V$ I want to want the smallest subspace of $A$ of $V$ such that $|A \cap S| \geq k $.
I suspect some variant of this problem would have already been studied but I have not been able to find it. Have anyone seen this or something similar before?
In general, this problem is hard. For instance, if we have a vector space over $GF(2)$, then checking whether there is a one-dimensional subspace $A$ with the desired property is as hard as learning parity with noise (LPN). LPN is conjectured to be hard: I believe there are subexponential-time algorithms, but as far as I know, there are no known polynomial-time algorithms. The hardness will depend on the specific parameters, i.e., the dimension of $V$, the size of $S$, and the value of $k$.
