Kronecker products, low-depth circuits, and matrix rigidity
Kronecker products, low-depth circuits, and matrix rigidity
复制标题
克罗内克积、低深度电路和矩阵刚性
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Josh Alman
中科院分区：
文献类型：
--
作者：
Josh Alman
对于一个矩阵M和一个正整数r，M的秩r刚性是使M的秩至多为r所必须改变的M的最小元素数。在复杂性理论中，刚性下界在许多领域有着广泛的应用，但刚性上界的应用却很少。在本文中，我们使用刚性上界证明了新的上界在几个不同的计算模型。我们的结果包括：-对任意d>1，在任意域F上，N × NWalsh-Hadamard变换有一个长度为O（d · N1 + 0.96/d）的深度为d的线性回路。Pudlák（2000）通过使用N中的幅值多项式的系数，绕过了已知的系数在N上有界的电路的Ω（d · N1 + 1/d）的下界。我们的构造也推广到由任何固定的2 × 2矩阵的Kronecker幂给出的线性变换。- N × N Walsh-Hadamard变换的线性电路的大小≤（1.81 + o（1））Nlog 2N，比标准快速Walsh-Hadamard变换的1.88Nlog2N的上界有所改进。- 一个新的刚性上界，证明了以下几类矩阵的刚性不足以用Valiant方法证明回路下界：（1）对任意域F和任意函数f：{0，1}n → F，矩阵Vf ∈ F2 n × 2n由下式给出，对于任何x，y ∈ {0，1}n，Vf[x，y] = f（x <$y），和（2）对于任何域F和任何固定大小的矩阵M1，.，Mn ∈ Fq × q，Kronecker积M1 Mn。这推广了最近的结果，非刚性，使用一个更简单的方法，避免了需要的多项式方法。- 递归线性变换（如傅立叶和沃尔什-阿达玛变换）与矩阵乘法电路之间的新联系。
For a matrix M and a positive integer r, the rank r rigidity of M is the smallest number of entries of M which one must change to make its rank at most r. There are many known applications of rigidity lower bounds to a variety of areas in complexity theory, but fewer known applications of rigidity upper bounds. In this paper, we use rigidity upper bounds to prove new upper bounds in a few different models of computation. Our results include: - For any d>1, and over any field F, the N × N Walsh-Hadamard transform has a depth-d linear circuit of size O(d · N1 + 0.96/d). This circumvents a known lower bound of Ω(d · N1 + 1/d) for circuits with bounded coefficients over ℂ by Pudlák (2000), by using coefficients of magnitude polynomial in N. Our construction also generalizes to linear transformations given by a Kronecker power of any fixed 2 × 2 matrix. - The N × N Walsh-Hadamard transform has a linear circuit of size ≤ (1.81 + o(1)) N log2 N, improving on the bound of ≈ 1.88 N log2 N which one obtains from the standard fast Walsh-Hadamard transform. - A new rigidity upper bound, showing that the following classes of matrices are not rigid enough to prove circuit lower bounds using Valiant’s approach: (1) for any field F and any function f : {0,1}n → F, the matrix Vf ∈ F2n × 2n given by, for any x,y ∈ {0,1}n, Vf[x,y] = f(x ∧ y), and (2) for any field F and any fixed-size matrices M1, …, Mn ∈ Fq × q, the Kronecker product M1 ⊗ M2 ⊗ ⋯ ⊗ Mn. This generalizes recent results on non-rigidity, using a simpler approach which avoids needing the polynomial method. - New connections between recursive linear transformations like Fourier and Walsh-Hadamard transforms, and circuits for matrix multiplication.
线性布尔运算符的复杂性
DOI：
10.1561/0400000063
发表时间：
2013
期刊：
Found. Trends Theor. Comput. Sci.
影响因子：
--
作者：
S. Jukna;I. Sergeev
通讯作者：
I. Sergeev