ECCC-Report TR09-134https://eccc.weizmann.ac.il/report/2009/134Comments and Revisions published for TR09-134en-usMon, 01 Mar 2010 19:57:20 +0200
Revision 1
| On matrix rigidity and locally self-correctable codes |
Zeev Dvir
https://eccc.weizmann.ac.il/report/2009/134#revision1We describe a new approach for the problem of finding {\rm rigid} matrices, as posed by Valiant [Val77], by connecting it to the, seemingly unrelated, problem of proving lower bounds for locally self-correctable codes. This approach, if successful, could lead to a non-natural property (in the sense of Razborov and Rudich [RR97]) implying super-linear 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 {\bf 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 {\em any} locally decodable code (and in particular Reed Muller codes) is rigid.
Mon, 01 Mar 2010 19:57:20 +0200https://eccc.weizmann.ac.il/report/2009/134#revision1
Paper TR09-134
| On matrix rigidity and locally self-correctable codes |
Zeev Dvir
https://eccc.weizmann.ac.il/report/2009/134We describe a new approach for the problem of finding {\rm rigid} matrices, as posed by Valiant [Val77], by connecting it to the, seemingly unrelated, problem of proving lower bounds for locally self-correctable codes. This approach, if successful, could lead to a non-natural property (in the sense of Razborov and Rudich [RR97]) implying super-linear 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 {\bf 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 {\em any} locally decodable code (and in particular Reed Muller codes) is rigid.
Thu, 10 Dec 2009 16:39:00 +0200https://eccc.weizmann.ac.il/report/2009/134