Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with tensors:
TR11-147 | 2nd November 2011
Michael Forbes, Amir Shpilka

On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing

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

TR16-025 | 26th February 2016
Shachar Lovett

The Fourier structure of low degree polynomials

Revisions: 1

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

TR20-030 | 9th March 2020
Matthias Christandl, Fran├žois Le Gall, Vladimir Lysikov, Jeroen Zuiddam

Barriers for Rectangular Matrix Multiplication

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

ISSN 1433-8092 | Imprint