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.

Authors

• Andreas Björklund
• Petteri Kaski

Keywords

• asymptotic rank conjecture
• directed Hamiltonian cycle
• randomized algorithm
• set cover conjecture
• set partitioning
• three-way partitioning