On matrix rigidity and locally self-correctable codes

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Scopus citations

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 languageEnglish (US)
Title of host publicationProceedings - 25th Annual IEEE Conference on Computational Complexity, CCC 2010
Pages291-298
Number of pages8
DOIs
StatePublished - 2010
Event25th Annual IEEE Conference on Computational Complexity, CCC 2010 - Cambridge, MA, United States
Duration: Jun 9 2010Jun 11 2010

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159

Other

Other25th Annual IEEE Conference on Computational Complexity, CCC 2010
Country/TerritoryUnited States
CityCambridge, MA
Period6/9/106/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