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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Since the seminal works of Strassen and Valiant it has been a central themein algebraic complexity theory to understand the relative complexity ofalgebraic problems, that is, to understand which algebraic problems (be itbilinear maps like matrix multiplication in Strassen's work, or the determinantand permanent polynomials in Valiant's) can be reduced to each other (under theappropriate notion of reduction).  In this paper we determine precisely how many independent scalarmultiplications can be reduced to a given bilinear map (this number is calledthe subrank, and extends the concept of matrix diagonalization to tensors), foressentially all (i.e. generic) bilinear maps. Namely, we prove for a genericbilinear map $T : V \times V \to V$ where $\dim(V) = n$ that $\theta(\sqrt{n})$independent scalar multiplications can be reduced to $T$. Our resultsignificantly improves on the previous upper bound from the work of Strassen(1991) and B\"urgisser (1990) which was $n^{2/3 + o(1)}$. Our full result ismuch more general and applies not only to bilinear maps and 3-tensors but alsoto $k$-tensors, for which we find that the generic subrank is$\theta(n^{1/(k-1)})$. Moreover, as an application we prove that the subrank isnot additive under the direct sum.  The subrank plays a central role in several areas of complexity theory(matrix multiplication algorithms, barrier results) and combinatorics (e.g.,the cap set problem and sunflower problem). As a consequence of our result weobtain several large separations between the subrank and tensor methods thathave received much interest recently, notably the slice rank (Tao, 2016),analytic rank (Gowers--Wolf, 2011; Lovett, 2018;Bhrushundi--Harsha--Hatami--Kopparty--Kumar, 2020), geometric rank(Kopparty--Moshkovitz--Zuiddam, 2020), and G-stable rank (Derksen, 2020).

Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors