__
Revision #1 to TR09-134 | 1st March 2010 19:57
__
#### On matrix rigidity and locally self-correctable codes

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

__
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: 3400

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.