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 -