2024/04/09 by Kaski, Petteri, Michałek, Mateusz · 1 citation
#14N07 #68W30 #Algebraic Geometry (math.AG) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.1 #FOS: Computer and information sciences #FOS: Mathematics #I.1.2
paper · doi:10.48550/arxiv.2404.06427
The exponent σ(T) of a tensor T∈\mathbbFd⊗\mathbbFd⊗\mathbbFd over a field \mathbbF captures the base of the exponential growth rate of the tensor rank of T under Kronecker powers. Tensor exponents are fundamental from the standpoint of algorithms and computational complexity theory; for example, the exponent ω of matrix multiplication can be characterized as ω=2σ(MM2), where MM2∈\mathbbF4⊗\mathbbF4⊗\mathbbF4 is the tensor that represents 2× 2 matrix multiplication. Our main result is an explicit construction of a sequence Ud of zero-one-valued tensors that is universal for the worst-case tensor exponent; more precisely, we show that σ(Ud)=σ(d) where σ(d)=sup_T∈\mathbbFd⊗\mathbbFd⊗\mathbbFdσ(T). We also supply an explicit universal sequence UΔ localised to capture the worst-case exponent σ(Δ) of tensors with support contained in Δ⊆ [d]×[d]× [d]; by combining such sequences, we obtain a universal sequence Td such that σ(Td)=1 holds if and only if Strassen's asymptotic rank conjecture [Progr. Math. 120 (1994)] holds for d. Finally, we show that the limit limd→∞σ(d) exists and can be captured as limd→∞ σ(Dd) for an explicit sequence (Dd)d=1^∞ of tensors obtained by diagonalisation of the sequences Ud. As our second result we relate the absence of polynomials of fixed degree vanishing on tensors of low rank, or more generally asymptotic rank, with upper bounds on the exponent σ(d). Using this technique, one may bound asymptotic rank for all tensors of a given format, knowing enough specific tensors of low asymptotic rank.