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. Specifically, 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 ((2−є)n|F|poly(n)). The k-Set Cover problem asks, given as input an n-element universe U, 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 is U. 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'om ‍[CCC ‍2012, ACM ‍Trans. ‍Algorithms ‍2016], there conjectured to follow from the Strong Exponential Time Hypothesis. We prove 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 ((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 fine-grained level, our results do not need the full strength of the asymptotic rank conjecture; it suffices that the conclusion of the conjecture holds approximately for a single 7× 7× 7 tensor.