2011/11/02 by Michael A. Forbes, Amir Shpilka
Computer Science · Engineering · Mathematics · #Electrical and Bioimpedance Tomography #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques #cs.CC #cs.IT #math.IT
paper · pdf · doi:10.1145/2213977.2213995
published as Proceedings of the 44th Symposium on Theory of Computing (2012), 163-172 · 55 pages
arxiv created 2011/11/02 · openalex publication_date 2012/05/19 · arxiv updated 2012/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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 [36]), 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 the first quasi-polynomial sized hitting sets for arbitrary tensors. 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 R) to recover a matrix M from few measurements, under the promise that M is rank ≤ r. In this work, we restrict our attention to recovering matrices that are exactly rank ≤ r using deterministic, non-adaptive, linear measurements, that are free from noise. Over R, we provide a set (of size 4nr) of such measurements, from which M can be recovered in O(rn2+r3n) field operations, and the number of measurements is essentially optimal. Further, the measurements can be taken to be all rank-1 matrices, or all sparse matrices. To the best of our knowledge no explicit constructions with those properties were known prior to this work.