Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR09-134 | 1st March 2010 19:57

On matrix rigidity and locally self-correctable codes

RSS-Feed




Revision #1
Authors: Zeev Dvir
Accepted on: 1st March 2010 19:57
Downloads: 1827
Keywords: 


Abstract:

We 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.



Changes to previous version:

small corrections/typos. updated references.


Paper:

TR09-134 | 10th December 2009 14:56

On matrix rigidity and locally self-correctable codes





TR09-134
Authors: Zeev Dvir
Publication: 10th December 2009 16:39
Downloads: 2319
Keywords: 


Abstract:

We 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.



ISSN 1433-8092 | Imprint