Locally Testble Codes

Locally Testble Codes. Cheraghchi, M. Master's thesis, EPFL, Lausanne, Switzerland, 2005.

Error correcting codes are combinatorial objects that allow reliable recovery of information in presence of errors by cleverly augmenting the original information with a certain amount of redundancy. The availability of efficient means of error detection is considered as a fundamental criterion for error correcting codes. Locally testable codes are families of error correcting codes that are highly robust against transmission errors and in addition provide super-efficient (sublinear time) probabilistic algorithms for error detection. In particular, the error detection algorithm probes the received sequence only at a small (or even constant) number of locations. There seems to be a trade-off between the amount of redundancy and the number of probes for the error detection procedure in locally testable codes. Even though currently best constructions allow reduction of redundancy to a nearly linear amount, it is not clear whether this can be further reduced to linear while preserving a constant number of probes. We study the formal notion of locally testable codes and survey several major results in this area. We also investigate closely related concepts, and in particular, polynomial low-degree tests and probabilistically checkable proofs.

@mastersthesis{ref:Che05:thesis,
  author =	 {Mahdi Cheraghchi},
  title =	 {Locally Testble Codes},
  school =	 {EPFL},
  url_Paper =
                  {https://eccc.weizmann.ac.il//static/books/Locally_Testable_Codes},
  institution =	 {IIF},
  publisher =	 {EPFL},
  address =	 {Lausanne, Switzerland},
  year =	 2005,
  abstract =	 { Error correcting codes are combinatorial objects
                  that allow reliable recovery of information in
                  presence of errors by cleverly augmenting the
                  original information with a certain amount of
                  redundancy.  The availability of efficient means of
                  error detection is considered as a fundamental
                  criterion for error correcting codes.  Locally
                  testable codes are families of error correcting
                  codes that are highly robust against transmission
                  errors and in addition provide super-efficient
                  (sublinear time) probabilistic algorithms for error
                  detection.  In particular, the error detection
                  algorithm probes the received sequence only at a
                  small (or even constant) number of locations.  There
                  seems to be a trade-off between the amount of
                  redundancy and the number of probes for the error
                  detection procedure in locally testable codes. Even
                  though currently best constructions allow reduction
                  of redundancy to a nearly linear amount, it is not
                  clear whether this can be further reduced to linear
                  while preserving a constant number of probes.  We
                  study the formal notion of locally testable codes
                  and survey several major results in this area. We
                  also investigate closely related concepts, and in
                  particular, polynomial low-degree tests and
                  probabilistically checkable proofs.  },
  keywords =	 {Error Correcting Codes, Locally Testable Codes,
                  Probabilistically Checkable Proofs (PCP), Low-Degree
                  Tests, Hardness of Approximation}
}

Downloads: 0