Abstract

Consider a matrix whose entries are polynomials in indeterminates x1,...,xm. On the one hand, we can substitute random values for the indeterminates x1,...,xm and compute the (generic) rank of the resulting matrix. On the other hand, we can compute its (symbolic) rank as a matrix with entries in the function field. Since rank is captured by vanishing of minors, a simple argument tells us that both computations yield the same answer. Further, elements in the function field can be expanded in terms of power series. The considerations above are crucial steps for the barriers for lower bounds (say for tensor rank) obtainable by reduction to matrix rank in the work of Efremenko, Garg, Oliveira and Wigderson.

In ongoing work with Garg, Oliveira and Wigderson, we are investigating (among other similar things) the possibility of obtaining lower bounds for higher order tensors by reduction to lower order tensors. In proving barriers for these, one needs analogous results for tensors whose entries are polynomials similar to the aforementioned case of matrices. The proof in the matrices case breaks down because tensor rank is not captured by vanishing of polynomials. But the statement remains true, indeed in greater generality. However, its proof now seems to require concepts and results from algebraic geometry, which I will explain in the talk. We hope of the general result will find even more applications in complexity theory.

No special background is assumed."

Video Recording