  We study the problem of obtaining efficient, deterministic, black-box
polynomial identity testing algorithms for depth-3 set-multilinear circuits
(over arbitrary fields). This class of circuits has an efficient,
deterministic, white-box polynomial identity testing algorithm (due to Raz and
Shpilka), but has no known such black-box algorithm. We recast this problem as
a question of finding a low-dimensional subspace H, spanned by rank 1 tensors,
such that any non-zero tensor in the dual space ker(H) has high rank. We obtain
explicit constructions of essentially optimal-size hitting sets for tensors of
degree 2 (matrices), and obtain quasi-polynomial sized hitting sets for
arbitrary tensors (but this second hitting set is less explicit).
  We also show connections to the task of performing low-rank recovery of
matrices, which is studied in the field of compressed sensing. Low-rank
recovery asks (say, over the reals) to recover a matrix M from few
measurements, under the promise that M is rank <=r. We also give a formal
connection between low-rank recovery and the task of sparse (vector) recovery:
any sparse-recovery algorithm that exactly recovers vectors of length n and
sparsity 2r, using m non-adaptive measurements, yields a low-rank recovery
scheme for exactly recovering nxn matrices of rank <=r, making 2nm non-adaptive
measurements. Furthermore, if the sparse-recovery algorithm runs in time \tau,
then the low-rank recovery algorithm runs in time O(rn^2+n\tau). We obtain this
reduction using linear-algebraic techniques, and not using convex optimization,
which is more commonly seen in compressed sensing algorithms. By using a dual
Reed-Solomon code, we are able to (deterministically) construct low-rank
recovery schemes taking 4nr measurements over the reals, such that the
measurements can be all rank-1 matrices, or all sparse matrices.
