  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 $\epsilon>0$ there
exists a positive integer constant $k$ such that no algorithm solves the
$k$-Set Cover problem in worst-case time $\mathcal{O}((2-\epsilon)^n|\mathcal
F|\operatorname{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
$\mathcal{O}((2-\delta)^n)$-time randomized algorithm for some constant
$\delta>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.
