Recent Progress on Matrix Rigidity - A Survey
Recent Progress on Matrix Rigidity - A Survey
复制标题
矩阵刚度的最新进展 - 一项调查
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
C. Ramya
中科院分区：
文献类型：
--
作者：
C. Ramya
矩阵刚性的概念是由Valiant（独立于Grigoriev）在计算线性变换的上下文中引入的。一个矩阵是刚性的，如果它远离任何低秩矩阵（根据汉明距离）。虽然我们知道刚性矩阵的存在，但得到刚性矩阵的显式构造一直是一个悬而未决的问题。近十年来，人们在理解矩阵刚性方面取得了巨大进展。在过去，几个矩阵，如Hadamard矩阵和傅立叶矩阵被证明是刚性的。最近，许多这些矩阵被证明具有低刚度。此外，最近还得到了E$和P^{NP}$类中刚性矩阵的几个显式构造。除此之外，矩阵刚性与通信复杂性、数据结构下限和纠错码等完全不同的领域有着惊人的联系。在这次调查中，我们提出了一组选定的结果，突出了最近的进展矩阵刚度和显着的连接到其他领域的理论计算机科学。
The concept of matrix rigidity was introduced by Valiant(independently by Grigoriev) in the context of computing linear transformations. A matrix is rigid if it is far(in terms of Hamming distance) from any matrix of low rank. Although we know rigid matrices exist, obtaining explicit constructions of rigid matrices have remained a long-standing open question. This decade has seen tremendous progress towards understanding matrix rigidity. In the past, several matrices such as Hadamard matrices and Fourier matrices were conjectured to be rigid. Very recently, many of these matrices were shown to have low rigidity. Further, several explicit constructions of rigid matrices in classes such as $E$ and $P^{NP}$ were obtained recently. Among other things, matrix rigidity has found striking connections to areas as disparate as communication complexity, data structure lower bounds and error-correcting codes. In this survey, we present a selected set of results that highlight recent progress on matrix rigidity and its remarkable connections to other areas in theoretical computer science.
影响因子：
1.4
作者：
Göös, Mika;Pitassi, Toniann;Watson, Thomas
通讯作者：
Watson, Thomas