@comment{ generated by }
@TechReport{ALGO-REPORT-2007-001,
abstract = {The rigidity function of a matrix is defined as the
minimum number of its entries that need to be changed in
order to reduce the rank of the matrix to below a given
parameter. Proving a strong enough lower bound on the
rigidity of a matrix implies a nontrivial lower bound on
the complexity of any linear circuit computing the set of
linear forms associated with it. However, although it is
shown that most matrices are rigid enough, no explicit
construction of a rigid family of matrices is known. In
this survey report we review the concept of rigidity and
some of its interesting variations as well as several
notable results related to that. We also show the
existence of highly rigid matrices constructed by
evaluation of bivariate polynomials over finite fields.},
affiliation = {EPFL},
author = {Cheraghchi, Mahdi},
details = {http://infoscience.epfl.ch/record/101081},
documenturl = {https://infoscience.epfl.ch/record/101081/files/Paper.pdf},
keywords = {Matrix Rigidity; Low Level Complexity; Circuit
Complexity; Linear Forms; algoweb_complexity},
oai-id = {oai:infoscience.epfl.ch:101081},
oai-set = {driver},
status = {PUBLISHED},
submitter = {276415; 276415},
title = {On {M}atrix {R}igidity and the {C}omplexity of {L}inear {F}orms},
unit = {ALGO},
year = 2005
}