### Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010 |

Pages | 291-298 |

Number of pages | 8 |

DOIs | |

State | Published - Aug 10 2010 |

Externally published | Yes |

Event | 25th Annual IEEE Conference on Computational Complexity, CCC 2010 - Cambridge, MA, United States Duration: Jun 9 2010 → Jun 11 2010 |

### Publication series

Name | Proceedings of the Annual IEEE Conference on Computational Complexity |
---|---|

ISSN (Print) | 1093-0159 |

### Other

Other | 25th Annual IEEE Conference on Computational Complexity, CCC 2010 |
---|---|

Country | United States |

City | Cambridge, MA |

Period | 6/9/10 → 6/11/10 |

### All Science Journal Classification (ASJC) codes

- Software
- Theoretical Computer Science
- Computational Mathematics

### Keywords

- Arithmetic circuits
- Complexity
- Matrices

## Fingerprint Dive into the research topics of 'On matrix rigidity and locally self-correctable codes'. Together they form a unique fingerprint.

## Cite this

*Proceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010*(pp. 291-298). [5497878] (Proceedings of the Annual IEEE Conference on Computational Complexity). https://doi.org/10.1109/CCC.2010.35