90 citations · 333 across the 51 of their papers we have counts for
10 papers · 1 filter
Towards finding hay in a haystack: explicit tensors of border rank greater than in
J. M. Landsberg, Mateusz Michałek
We write down an explicit sequence of tensors in , for all sufficiently large, having border rank at least , overcoming a longstanding barrier…
Rank and border rank of Kronecker powers of tensors and Strassen's laser method
Austin Conner, Fulvio Gesmundo, Joseph M. Landsberg +1
We prove that the border rank of the Kronecker square of the little Coppersmith-Winograd tensor is the square of its border rank for and that the border rank of…
The complexity of matrix multiplication: developments since 2014. Extended abstract of 2018 Oberwolfach Complexity meeting plenary lecture
Joseph M. Landsberg
This is an overview of recent developments regarding the complexity of matrix multiplication, with an emphasis on the uses of algebraic geometry and representation theory in comple…
The geometry of rank decompositions of matrix multiplication II: matrices
Grey Ballard, Christian Ikenmeyer, J. M. Landsberg +1
This is the second in a series of papers on rank decompositions of the matrix multiplication tensor. We present new rank decompositions for the matrix multiplicati…
Explicit polynomial sequences with maximal spaces of partial derivatives and a question of K. Mulmuley
Fulvio Gesmundo, Joseph M. Landsberg
We answer a question of K. Mulmuley: In [Efremenko-Landsberg-Schenck-Weyman] it was shown that the method of shifted partial derivatives cannot be used to separate the padded perma…
The geometry of rank decompositions of matrix multiplication I: 2x2 matrices
Luca Chiantini, Christian Ikenmeyer, J. M. Landsberg +1
This is the first in a series of papers on rank decompositions of the matrix multiplication tensor. In this paper we: establish general facts about rank decompositions of tensors,…
Complexity of linear circuits and geometry
Fulvio Gesmundo, Jonathan Hauenstein, Christian Ikenmeyer +1
We use algebraic geometry to study matrix rigidity, and more generally, the complexity of computing a matrix-vector product, continuing a study initiated by Kumar, et. al. We (i) e…
Equations for lower bounds on border rank
Jonathan D. Hauenstein, Christian Ikenmeyer, J. M. Landsberg
We present new methods for determining polynomials in the ideal of the variety of bilinear maps of border rank at most r. We apply these methods to several cases including the case…
Holographic algorithms without matchgates
J. M. Landsberg, Jason Morton, Serguei Norine
The theory of holographic algorithms, which are polynomial time algorithms for certain combinatorial counting problems, yields insight into the hierarchy of complexity classes. In…
Geometry and the complexity of matrix multiplication
J. M. Landsberg
We survey results in algebraic complexity theory, focusing on matrix multiplication. Our goals are (i.) to show how open questions in algebraic complexity theory are naturally pose…