Amir Shpilka
On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing.
Fri, 11/04/2011 - 15:01 — SomNambulAuthors: Amir Shpilka, Michael A. Forbes
Subjects: Computational Complexity
AbstractWe 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.On the Structure of Cubic and Quartic Polynomials.
Fri, 08/21/2009 - 19:51 — SomNambulAuthors: Elad Haramaty, Amir Shpilka
Subjects: Combinatorics
AbstractIn this paper we study the structure of polynomials of degree three and four
that have high bias or high Gowers norm, over arbitrary prime fields. In
particular we obtain the following results.1. We give a canonical representation for degree three or four polynomials
that have a significant bias (i.e. they are not equidistributed). This result
generalizes the corresponding results from the theory of quadratic forms. It
also significantly improves the results of Green and Tao and Kaufman and Lovett
for such polynomials.
User login
