论文标题
矩阵刚度的最新进展 - 调查
Recent Progress on Matrix Rigidity -- A Survey
论文作者
论文摘要
矩阵刚度的概念是在计算线性转换的背景下由Valiant（由Grigoriev独立）引入的。如果矩阵刚度是刚性的，则该基质（就锤距而言）与低等级的任何矩阵的距离很远。尽管我们知道存在刚性矩阵，但获得刚性矩阵的明确结构仍然是一个长期的开放问题。这十年在理解矩阵刚度方面取得了巨大进步。过去，将诸如Hadamard矩阵和傅立叶矩阵等几个矩阵猜想为刚性。最近，许多这些矩阵被证明具有较低的刚度。此外，最近获得了诸如$ e $和$ 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.
