Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications
Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications
复制标题
迭代矩阵乘法的小深度多线性公式下界及其应用
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
S. Srinivasan
中科院分区：
文献类型：
--
作者：
Suryajith Chillara;N. Limaye;S. Srinivasan
在本文中，我们研究了乘以$ d $ d $ 2 $ 2 imes 2 $矩阵的代数公式复杂性，表示为$ mathrm {imm} _ {D} $只要公式是多线性的，在任何深度都可以改善。
正式地，对于每个深度$ delta leq log d $，我们表明任何产品深度$ delta $ delta $多连接公式用于$ shimrm {imm} _d $必须具有size $ exp（omega（delta d^{1/delta}））） 。$也从此遵循的是，对于上述形式的同一多项式的产品深度$ delta $的任何多线性电路都必须具有大小$ exp（omega（d^{1/delta}））。尤其是，$ mathrm {imm} _d $的任何多项式大小的多线性公式都必须具有深度$ omega（log d）$，以及任何多项式的多项式多项式$ MATHRM {imm} _d $的电路必须具有深度$ OMEGA（log d/log log D）。$这两个边界都紧紧恒定因素。
1。缩减深度：Brent的众所周知的结果（JACM 1974）意味着任何大小$ s $的公式都可以转换为尺寸$ s^{o（1）} $和深度$ O（log s） ）$;此外，多线性公式的这种降低继续保持。我们的下限意味着多线性设置中的任何深度降低都无法将深度降低到$ o（log s）$，而没有大小的超级单位爆炸。
2。与一般公式的分离：我们的结果，以及$ mathrm {imm} _ {d} $的非平凡的上限，这是Gupta，Kamath，Kamath，Kayal和Saptharishi（Sicomp 2016）所暗示的尺寸$ s $和产品深度$ delta = o（log S），$大小$ s $和product-depth $ delta $的通用公式在基础字段具有特征性零时，可以转换为$ s^{omega（1）} $ $ s^{omega（1）} $的多线性公式，$。
In this paper, we study the algebraic formula complexity of multiplying $d$ many $2 imes 2$ matrices, denoted $mathrm{IMM}_{d}$, and show that the well-known divide-and-conquer algorithm cannot be significantly improved at any depth, as long as the formulas are multilinear.
Formally, for each depth $Delta leq log d$, we show that any product-depth $Delta$ multilinear formula for $mathrm{IMM}_d$ must have size $exp(Omega(Delta d^{1/Delta})).$ It also follows from this that any multilinear circuit of product-depth $Delta$ for the same polynomial of the above form must have a size of $exp(Omega(d^{1/Delta})).$ In particular, any polynomial-sized multilinear formula for $mathrm{IMM}_d$ must have depth $Omega(log d)$, and any polynomial-sized multilinear circuit for $mathrm{IMM}_d$ must have depth $Omega(log d/log log d).$ Both these bounds are tight up to constant factors.
1. Depth-reduction: A well-known result of Brent (JACM 1974) implies that any formula of size $s$ can be converted to one of size $s^{O(1)}$ and depth $O(log s)$; further, this reduction continues to hold for multilinear formulas. Our lower bound implies that any depth-reduction in the multilinear setting cannot reduce the depth to $o(log s)$ without a superpolynomial blow-up in size.
2. Separations from general formulas: Our result, along with a non-trivial upper bound for $mathrm{IMM}_{d}$ implied by a result of Gupta, Kamath, Kayal and Saptharishi (SICOMP 2016), shows that for any size $s$ and product-depth $Delta = o(log s),$ general formulas of size $s$ and product-depth $Delta$ cannot be converted to multilinear formulas of size $s^{omega(1)}$ and product-depth $Delta,$ when the underlying field has characteristic zero.