  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.
