2023/10/18 by Andreas Björklund, Björklund, Andreas, Petteri Kaski +1
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.2310.11926
openalex publication_date 2023/10/18 · openalex created_date 2023/10/21 · openalex updated_date 2026/07/28
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 O((2-ε)n|\mathcal F|poly(n)). The k-Set Cover problem asks, given as input an n-element universe U, a family \mathcal 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 \mathcal F whose union is U. The conjecture was formulated by Cygan et al. in the monograph Parameterized Algorithms [Springer, 2015] but was implicit as a hypothesis already in Cygan et al. [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 a 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.