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.