The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both True

Strassen’s asymptotic rank conjecture [Progr. Math. 120 (1994)] claims a strong submultiplicative upper bound on the rank of a three-tensor obtained as an iterated Kronecker product of a constant-size base tensor. The conjecture, if true, most notably would put square matrix multiplication in quadratic time. We note here that some more-or-less unexpected algorithmic results in the area of exponential-time algorithms would also follow. Speci cally, we study the so-called set cover conjecture, which states that for any ϵ > 0 there exists a positive integer constant k such that no algorithm solves the k-Set Cover problem in worst-case time O((2 −ϵ)n|F |poly(n)). The k-Set Cover problem asks, given as input an n-element universeU, a family F of size-at-most-k subsets of U, and a positive integer t, whether there is a subfamily of at most t sets in F whose union isU. The conjecture was formulated by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, and Saurabh in the monograph Parameterized Algorithms [Springer, 2015], but was implicit as a hypothesis already in Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, and Wahlström [CCC 2012, ACM Trans. Algorithms 2016], there conjectured to follow from the Strong Exponential Time Hypothesis. Weprove that if the asymptotic rank conjecture is true, then the set cover conjecture is false. Using a reduction by Krauthgamer and Trabelsi [STACS 2019], in this scenario we would also get an O((2 −δ)n)-time randomized algorithm for some constant δ > 0 for another well-studied problem for which no such algorithm is known, namely that of deciding whether a given n-vertex directed graph has a Hamiltonian cycle. At a ne-grained level, our results do not need the full strength of the asymptotic rank conjecture; it su ces that the conclusion of the conjecture holds approximately for a single 7 × 7 × 7 tensor.