A stronger connection between the asymptotic rank conjecture and the set cover conjecture

2023/11/05 by Kevin Pratt, Pratt, Kevin · 5 citations
Mathematics · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Mathematical Approximation and Integration #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.2311.02774

openalex publication_date 2023/11/05 · openalex created_date 2023/11/08 · openalex updated_date 2026/07/28

Abstract

We give a short proof that Strassen's asymptotic rank conjecture implies that for every ε > 0 there exists a (3/2^2/3 + ε)ⁿ-time algorithm for set cover on a universe of size n with sets of bounded size. This strengthens and simplifies a recent result of Björklund and Kaski that Strassen's asymptotic rank conjecture implies that the set cover conjecture is false. From another perspective, we show that the set cover conjecture implies that a particular family of tensors T_n ∈ ℂ^N ⊗ ℂ^N ⊗ ℂ^N has asymptotic rank greater than N^1.08. Furthermore, if one could improve a known upper bound of (1)/(2)8ⁿ on the tensor rank of T_n to (2)/(9 ⋅ n)8ⁿ for any n, then the set cover conjecture is false.

Cited by

• k-SUM Hardness Implies Treewidth-SETH
• Faster algorithms for k-Orthogonal Vectors in low dimension
• Faster Convolutions: Yates and Strassen Revisited
• Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?
• Kronecker scaling of tensors with applications to arithmetic circuits and algorithms

Related

• The Asymptotic Rank Conjecture and the Set Cover Conjecture are not Both True
• Finding Large Set Covers Faster via the Representation Method
• Asymptotic tensor rank is characterized by polynomials
• A gap in the slice rank of k-tensors
• On the construction of a counterexample to Strassen's rank additivity conjecture