A Stronger Connection between the Asymptotic Rank Conjecture and the Set Cover Conjecture

We give a short proof that Strassen’s asymptotic rank conjecture implies that for every ε > 0 there exists a (3/22/3 + ε)n-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'orklund 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 Tn ∈ ℂN ⊗ ℂN ⊗ ℂN has asymptotic rank greater than N1.08. Furthermore, if one could improve a known upper bound of 8n on the tensor rank of Tn to 2/9 · n8n for any n, then the set cover conjecture is false.