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] 的工作。 我们的方法来自通俗代数和复杂度理论。

0
下载
关闭预览

相关内容

Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
163+阅读 · 2019年10月12日
【新书】Python编程基础,669页pdf
专知会员服务
197+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年11月29日
Arxiv
0+阅读 · 2021年11月25日
Arxiv
0+阅读 · 2021年11月25日
VIP会员
相关主题
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员