TY - GEN
T1 - On matrix rigidity and locally self-correctable codes
AU - Dvir, Zeev
PY - 2010
Y1 - 2010
N2 - We describe a new approach for the problem of finding rigid matrices, as posed by Valiant [Val77], by connecting it to the, seemingly unrelated, problem of proving lower bounds for linear locally self-correctable codes. This approach, if successful, could lead to a non-natural property (in the sense of Razborov and Rudich [RR97]) implying superlinear lower bounds for linear functions in the model of logarithmic-depth arithmetic circuits. Our results are based on a lemma saying that, if the generating matrix of a locally decodable code is not rigid, then it defines a locally self-correctable code with rate close to one. Thus, showing that such codes cannot exist will prove that the generating matrix of any locally decodable code (and in particular Reed Muller codes) is rigid.
AB - We describe a new approach for the problem of finding rigid matrices, as posed by Valiant [Val77], by connecting it to the, seemingly unrelated, problem of proving lower bounds for linear locally self-correctable codes. This approach, if successful, could lead to a non-natural property (in the sense of Razborov and Rudich [RR97]) implying superlinear lower bounds for linear functions in the model of logarithmic-depth arithmetic circuits. Our results are based on a lemma saying that, if the generating matrix of a locally decodable code is not rigid, then it defines a locally self-correctable code with rate close to one. Thus, showing that such codes cannot exist will prove that the generating matrix of any locally decodable code (and in particular Reed Muller codes) is rigid.
KW - Arithmetic circuits
KW - Complexity
KW - Matrices
UR - http://www.scopus.com/inward/record.url?scp=77955233118&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77955233118&partnerID=8YFLogxK
U2 - 10.1109/CCC.2010.35
DO - 10.1109/CCC.2010.35
M3 - Conference contribution
AN - SCOPUS:77955233118
SN - 9780769540603
T3 - Proceedings of the Annual IEEE Conference on Computational Complexity
SP - 291
EP - 298
BT - Proceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010
T2 - 25th Annual IEEE Conference on Computational Complexity, CCC 2010
Y2 - 9 June 2010 through 11 June 2010
ER -