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

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Determining the asymptotic algebraic complexity of matrix multiplication,succinctly represented by the matrix multiplication exponent $\omega$, is acentral problem in algebraic complexity theory. The best upper bounds on$\omega$, leading to the state-of-the-art $\omega \leq 2.37..$, have beenobtained via the laser method of Strassen and its generalization by Coppersmithand Winograd. Recent barrier results show limitations for these and relatedapproaches to improve the upper bound on $\omega$.  We introduce a new and more general barrier, providing stronger limitationsthan in previous work. Concretely, we introduce the notion of "irreversibility"of a tensor and we prove (in some precise sense) that any approach that uses anirreversible tensor in an intermediate step (e.g., as a starting tensor in thelaser method) cannot give $\omega = 2$. In quantitative terms, we prove thatthe best upper bound achievable is lower bounded by two times theirreversibility of the intermediate tensor. The quantum functionals andStrassen support functionals give (so far, the best) lower bounds onirreversibility. We provide lower bounds on the irreversibility of keyintermediate tensors, including the small and big Coppersmith--Winogradtensors, that improve limitations shown in previous work. Finally, we discussbarriers on the group-theoretic approach in terms of "monomial"irreversibility.

Barriers for fast matrix multiplication from irreversibility