English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Strassen's asymptotic rank conjecture [Progr. Math. 120 (1994)] claims astrong submultiplicative upper bound on the rank of a three-tensor obtained asan 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 areaof exponential-time algorithms would also follow. Specifically, we study theso-called set cover conjecture, which states that for any $\epsilon>0$ thereexists a positive integer constant $k$ such that no algorithm solves the$k$-Set Cover problem in worst-case time $\mathcal{O}((2-\epsilon)^n|\mathcalF|\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 Cyganet al. in the monograph Parameterized Algorithms [Springer, 2015] but wasimplicit as a hypothesis already in Cygan et al. [CCC 2012, ACM Trans.Algorithms 2016], there conjectured to follow from the Strong Exponential TimeHypothesis. We prove that if the asymptotic rank conjecture is true, then theset 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 isknown, namely that of deciding whether a given $n$-vertex directed graph has aHamiltonian cycle.

The Asymptotic Rank Conjecture and the Set Cover Conjecture are not Both True