2025/11/04 by Dvir, Zeev
Mathematics · #Algebraic Geometry and Number Theory #Combinatorics (math.CO) #Commutative Algebra and Its Applications #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Tensor decomposition and applications
paper · doi:10.48550/arxiv.2511.02670
openalex publication_date 2025/11/04 · openalex created_date 2025/11/06 · openalex updated_date 2026/07/28
We prove a lower bound on the rank of tensors constructed from families of linear maps that `expand' the dimension of every subspace. Such families, called \em dimension expanders have been studied for many years with several known explicit constructions. Using these constructions we show that one can construct an explicit [D]× [n] × [n]-tensor with rank at least (2 - ε)n, with D a constant depending on ε. Our results extend to border rank over the real or complex numbers.