Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

#### On matrix rigidity and locally self-correctable codes

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