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 ... more >>>

We study the structure of the Fourier coefficients of low degree multivariate polynomials over finite fields. We consider three properties: (i) the number of nonzero Fourier coefficients; (ii) the sum of the absolute value of the Fourier coefficients; and (iii) the size of the linear subspace spanned by the nonzero ... more >>>

We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give optimal algorithms. In fact, we prove a precise numerical barrier for this method. Our barrier improves the previously ... more >>>

Hyperdeterminants are high dimensional analogues of determinants, associated with tensors of formats generalizing square matrices. First conceived for $2\times 2\times 2$ tensors by Cayley, they were developed in generality by Gelfand, Kapranov and Zelevinsky. Yet, hyperdeterminants in three or more dimensions are long conjectured to be VNP-Hard to compute, akin ... more >>>