28 citations · 112 across the 18 of their papers we have counts for
4 papers · 1 filter
On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing
Michael A. Forbes, Amir Shpilka
We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing algorithms for depth-3 set-multilinear circuits (over arbitrary fields). This clas…
Improved Soundness for QMA with Multiple Provers
Alessandro Chiesa, Michael A. Forbes
We present three contributions to the understanding of QMA with multiple provers: 1) We give a tight soundness analysis of the protocol of [Blier and Tapp, ICQNM '09], yielding a s…
Square root Bound on the Least Power Non-residue using a Sylvester-Vandermonde Determinant
Michael Forbes, Neeraj Kayal, Rajat Mittal +1
We give a new elementary proof of the fact that the value of the least power non-residue in an arithmetic progression , over a prime field $\F_p$, is…
Tensor Rank: Some Lower and Upper Bounds
Boris Alexeev, Michael Forbes, Jacob Tsimerman
The results of Strassen and Raz show that good enough tensor rank lower bounds have implications for algebraic circuit/formula lower bounds. We explore tensor rank lower and upper…