Determining the matrix multiplication exponent $\omega$ is one of the greatest open problems in theoretical computer science. We show that it is impossible to prove $\omega = 2$ by starting with structure tensors of modules of fixed degree and using arbitrary restrictions. It implies that the same is impossible by starting with $1_A$-generic non-diagonal tensors of fixed size with minimal border rank. This generalizes the work of Bl\"aser and Lysikov [3]. Our methods come from both commutative algebra and complexity theory.
翻译：确定矩阵乘法指数$\ omega$是理论计算机科学中最大的尚未解决的问题之一。 我们表明,从固定度模块结构的数以万计开始,使用任意限制,无法证明$\ omega = 2美元。 这意味着,从1美元A$- generic非对角尺寸固定且边界级别最小的数值开始,就不可能证明美元= 2美元。 这概括了 Bl\ “aser” 和 Lysikov [3] 的工作。 我们的方法来自通俗代数和复杂度理论。
相关内容
Arxiv
0+阅读 · 2022年4月19日
Arxiv
0+阅读 · 2022年4月15日
Arxiv
0+阅读 · 2022年4月14日
Arxiv
11+阅读 · 2021年9月3日
相关VIP内容
相关资讯
相关论文
Arxiv
0+阅读 · 2022年4月19日
Arxiv
0+阅读 · 2022年4月15日
Arxiv
0+阅读 · 2022年4月14日
Arxiv
11+阅读 · 2021年9月3日
微信扫码咨询专知VIP会员