TY - GEN
T1 - The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both True
AU - Björklund, Andreas
AU - Kaski, Petteri
PY - 2024/6/10
Y1 - 2024/6/10
N2 - 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.
AB - 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.
KW - asymptotic rank conjecture
KW - directed Hamiltonian cycle
KW - randomized algorithm
KW - set cover conjecture
KW - set partitioning
KW - three-way partitioning
UR - https://doi.org/10.1145/3618260.3649656
U2 - 10.1145/3618260.3649656
DO - 10.1145/3618260.3649656
M3 - Article in proceedings
BT - STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing
ER -