  We study the problem of finding elements in the intersection of an arbitrary
conic variety in $\mathbb{F}^n$ with a given linear subspace (where
$\mathbb{F}$ can be the real or complex field). This problem captures a rich
family of algorithmic problems under different choices of the variety. The
special case of the variety consisting of rank-1 matrices already has strong
connections to central problems in different areas like quantum information
theory and tensor decompositions. This problem is known to be NP-hard in the
worst case, even for the variety of rank-1 matrices.
  Surprisingly, despite these hardness results we develop an algorithm that
solves this problem efficiently for "typical" subspaces. Here, the subspace $U
\subseteq \mathbb{F}^n$ is chosen generically of a certain dimension,
potentially with some generic elements of the variety contained in it. Our main
result is a guarantee that our algorithm recovers all the elements of $U$ that
lie in the variety, under some mild non-degeneracy assumptions on the variety.
As corollaries, we obtain the following new results:
  $\bullet$ Polynomial time algorithms for several entangled subspaces problems
in quantum entanglement, including determining r-entanglement, complete
entanglement, and genuine entanglement of a subspace. While all of these
problems are NP-hard in the worst case, our algorithm solves them in polynomial
time for generic subspaces of dimension up to a constant multiple of the
maximum possible.
  $\bullet$ Uniqueness results and polynomial time algorithmic guarantees for
generic instances of a broad class of low-rank decomposition problems that go
beyond tensor decompositions. Here, we recover a decomposition of the form
$\sum_{i=1}^R v_i \otimes w_i$, where the $v_i$ are elements of the variety
$X$. This implies new uniqueness results and genericity guarantees even in the
special case of tensor decompositions.
