5
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Okei, that certainly seems very related. thanks $\endgroup$
    – Sander
    Mar 8 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.