Probabilistic rank and matrix rigidity
Probabilistic rank and matrix rigidity
复制标题
概率秩和矩阵刚性
DOI：
10.1145/3055399.3055484
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Richard Ryan Williams
中科院分区：
文献类型：
--
作者：
Josh Alman;Richard Ryan Williams
我们考虑矩阵的概率秩和概率符号秩的概念，它度量了一个矩阵可以被低秩阵概率表示的程度。我们演示了几个与矩阵刚性、通信复杂性和电路下界之间的联系。最有趣的结果是：沃尔什-阿达玛变换不是很严格。我们给出了一族矩阵的刚性的令人惊讶的上界，其刚性已被广泛研究，并被猜想是高度刚性的。对于2n×2n Walsh-Hadamard变换Hn(也称为西尔维斯特矩阵，又名。内积模2的通信矩阵，我们展示了如何只修改每行中的2个对数n个条目，并且对于任何域上的所有小ε；0，使Hn的秩降到2n(1-Ω(ε2/εε(1/ε))以下。也就是说，不可能用L.Valiant的矩阵刚性方法证明Hadamard矩阵(如Hn)的算术回路下界。我们还证明了具有较小目标阶的Hn的非平凡刚性上界。矩阵刚性和阈值电路下界。我们给出了刚性矩阵对于布尔电路复杂性的新结果。首先，我们证明了显式n×n布尔矩阵在n2/2(Logn)δ/2修改项之后保持至少2(Logn)1-δ的阶(在任何域上，对于任何δ>；0)将产生一个显式函数，该显式函数不具有具有两层任意线性门限门的次二次大小的ac0电路。其次，我们证明了ℝ上的显式0/1矩阵比最著名的符号秩刚性下界要严格一些，这意味着在两层上都有任意权的一类臭名昭著的困难的深度二阶线性阈值电路的指数门下界。特别地，我们证明了由这些看似困难的电路类定义的矩阵实际上分别具有低概率秩和符号秩.沟通、概率等级和刚性之间的等价性。自Razborov[1989]以来，人们已经知道显式刚性下界可以解决通信复杂性中长期存在的下界问题，但似乎可以在不对矩阵刚性取得进展的情况下证明通信下界。我们证明了对于每个以自然方式随机自约的函数f(以内积mod 2为例)，f的通信复杂性的界(在精确的技术意义上)等价于f的矩阵的刚性的界，通过与概率等级的等价。
We consider a notion of probabilistic rank and probabilistic sign-rank of a matrix, which measure the extent to which a matrix can be probabilistically represented by low-rank matrices. We demonstrate several connections with matrix rigidity, communication complexity, and circuit lower bounds. The most interesting outcomes are: The Walsh-Hadamard Transform is Not Very Rigid. We give surprising upper bounds on the rigidity of a family of matrices whose rigidity has been extensively studied, and was conjectured to be highly rigid. For the 2n X 2n Walsh-Hadamard transform Hn (a.k.a. Sylvester matrices, a.k.a. the communication matrix of Inner Product modulo 2), we show how to modify only 2ε n entries in each row and make the rank of Hn drop below 2n(1-Ω(ε2/log(1/εε))), for all small ε > 0, over any field. That is, it is not possible to prove arithmetic circuit lower bounds on Hadamard matrices such as Hn, via L. Valiant's matrix rigidity approach. We also show non-trivial rigidity upper bounds for Hn with smaller target rank. Matrix Rigidity and Threshold Circuit Lower Bounds. We give new consequences of rigid matrices for Boolean circuit complexity. First, we show that explicit n X n Boolean matrices which maintain rank at least 2(logn)1-δ after n2/2(logn)δ/2 modified entries (over any field, for any δ > 0) would yield an explicit function that does not have sub-quadratic-size AC0 circuits with two layers of arbitrary linear threshold gates. Second, we prove that explicit 0/1 matrices over ℝ which are modestly more rigid than the best known rigidity lower bounds for sign-rank would imply exponential-gate lower bounds for the infamously difficult class of depth-two linear threshold circuits with arbitrary weights on both layers. In particular, we show that matrices defined by these seemingly-difficult circuit classes actually have low probabilistic rank and sign-rank, respectively. An Equivalence Between Communication, Probabilistic Rank, and Rigidity. It has been known since Razborov [1989] that explicit rigidity lower bounds would resolve longstanding lower-bound problems in communication complexity, but it seemed possible that communication lower bounds could be proved without making progress on matrix rigidity. We show that for every function f which is randomly self-reducible in a natural way (the inner product mod 2 is an example), bounding the communication complexity of f (in a precise technical sense) is equivalent to bounding the rigidity of the matrix of f, via an equivalence with probabilistic rank.