Geometry and Complexity Theory

DOI10.1017/9781108183192zbMath1387.68002OpenAlexW2763778230MaRDI QIDQ5349345

Publication date: 24 August 2017

Full work available at URL: https://semanticscholar.org/paper/1d1648cb5d1b89fef5e7dbd46dbe74715402a4d2

complexity matrix multiplication Valiant's hypothesis

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Research exposition (monographs, survey articles) pertaining to algebraic geometry (14-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Related Items (45)

Strict inclusions of high rank loci ⋮ New elementary components of the Gorenstein locus of the Hilbert scheme of points ⋮ Universal points in the asymptotic spectrum of tensors ⋮ Tensors in computations ⋮ Bounds on complexity of matrix multiplication away from Coppersmith-Winograd tensors ⋮ On the geometry of geometric rank ⋮ Secant varieties of toric varieties arising from simplicial complexes ⋮ Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science ⋮ Geometry and the complexity of matrix multiplication ⋮ Distinguishing secant from cactus varieties ⋮ On the structure tensor of \(\mathfrak{sl}_n\) ⋮ On the geometry of tensor network states of \(2\times N\) grids ⋮ Ranks and symmetric ranks of cubic surfaces ⋮ Dimension of tensor network varieties ⋮ Learning algebraic models of quantum entanglement ⋮ Concise tensors of minimal border rank ⋮ Partial Degeneration of Tensors ⋮ Bad and good news for Strassen's laser method: border rank of \(\mathrm{Perm}_3\) and strict submultiplicativity ⋮ Numerical stability and tensor nuclear norm ⋮ New lower bounds for matrix multiplication and ⋮ Interactions of computational complexity theory and mathematics ⋮ Plethysm and fast matrix multiplication ⋮ Waring, tangential and cactus decompositions ⋮ Lower bounds on the rank and symmetric rank of real tensors ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Border Rank Is Not Multiplicative under the Tensor Product ⋮ Barriers for Rank Methods in Arithmetic Complexity ⋮ On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions ⋮ Towards a geometric approach to Strassen's asymptotic rank conjecture ⋮ New ways to multiply \(3 \times 3\)-matrices ⋮ The geometry of rank decompositions of matrix multiplication. II: \(3 \times 3\) matrices ⋮ Unnamed Item ⋮ Orthogonal tensor decomposition and orbit closures from a linear algebraic perspective ⋮ Identifiability of rank-3 tensors ⋮ Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties) ⋮ Apolarity, border rank, and multigraded Hilbert scheme ⋮ Rank and border rank of Kronecker powers of tensors and Strassen's laser method ⋮ On symmetries of tensor decompositions for the commutator of \(2 \times 2\) matrices ⋮ Uniform matrix product states from an algebraic geometer's point of view ⋮ Linear projections of the Vandermonde polynomial ⋮ The Hitchhiker guide to: secant varieties and tensor decomposition ⋮ Hermitian K-theory via oriented Gorenstein algebras ⋮ Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication ⋮ Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication

This page was built for publication: Geometry and Complexity Theory